92. Reverse Linked List II

Reverse a linked list from positionmton. Do it in-place and in one-pass.

For example:
Given1->2->3->4->5->NULL,m= 2 andn= 4,

return1->4->3->2->5->NULL.

Note:
Givenm,nsatisfy the following condition:
1 ≤m≤n≤ length of list.

思路: 找到位置套一套

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m==n||head==null||head.next==null){
            return head;
        }

        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode prev = newHead;
        ListNode curr = head;
        for (int i=1;i<m;i++){
            prev = curr;
            curr = curr.next;
        }

        ListNode smallHead = null;
        ListNode smallTail = curr;
        for (int j=m;j<=n;j++){
            ListNode next = curr.next;
            curr.next = smallHead;
            smallHead = curr;
            curr = next;
        }

        prev.next = smallHead;
        smallTail.next = curr;

        return newHead.next;
    }
}