[LeetCode] 92. Reverse Linked List II

Posted on | In

Problem

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

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

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

Explanation

  1. First, we need to know mNode and nNode’s correct position.

  2. We need to create one more node that is pointing at the previous of mNode called preM. For example, linked list is 1->2->3->4->5, m = 2 n = 4, so preM points at element 1, mNode points at element 2, nNode points at element 4. Then, we move mNode to the next of nNode, then update mNode to its next element, and repeat this process until mNode and nNode point at the same element. We can illustrate this process below:

    1
    2
    3
     1->2->3->4->5
 1->3->4->2->5
 1->4->3->2->5

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode preM = dummy;
        ListNode mNode = head;
        ListNode nNode = head;
        for (int i = 1; i < m; i++) {
            preM = mNode;
            mNode = mNode.next;
        }
        for (int i = 1; i < n; i++) {
            nNode = nNode.next;
        }

        while (mNode != nNode) {
            preM.next = mNode.next;
            mNode.next = nNode.next;
            nNode.next = mNode;
            mNode = preM.next;
        }

        return dummy.next;
    }
}