[LeetCode] Problem 92 - Reverse Linked List II

Posted on | In ,

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

Note

1 ≤ m ≤ n ≤ length of list.

Example

Input: 1->2->3->4->5->NULL, m = 2, n = 4

Output: 1->4->3->2->5->NULL

Code

1
2
3
4
5
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode mPrevNode = dummy;

    for (int i = 1; i < m; i++)
        mPrevNode = mPrevNode.next;

    ListNode mNode = mPrevNode.next;
    ListNode nNode = mNode;
    ListNode nPostNode = nNode.next;

    for (int i = m; i < n; i++) {
        ListNode next = nPostNode.next;
        nPostNode.next = nNode;
        nNode = nPostNode;
        nPostNode = next;
    }

    mNode.next = nPostNode;
    mPrevNode.next = nNode;

    return dummy.next;
}