Question:

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Thinking:

It’s similar with Reverse Linked List, only thing different is to limit the range. So we should to find the start of the reversed linked list and record its previous node. Also, we should add a dummy node for easily operator with the first node. Then use three points as usual pre, cur and next to operate and change the nodes’ next pointers.

Solution:

public ListNode reverseBetween(ListNode head, int m, int n) {
    if (m == n)
        return head;
    ListNode prehead = new ListNode(0);//dummy
    prehead.next = head;
    ListNode pre = prehead;
    ListNode cur = head;
    int idx = 1;

    while (idx < m) {
        pre = cur;
        cur = cur.next;
        idx++;
    }
    ListNode prerever = pre;
    ListNode next = null;
    pre = cur;
    cur = cur.next;
    while (idx < n) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
        idx++;
    }
    prerever.next.next = cur;
    prerever.next = pre;


    return prehead.next;
}