[LeetCode] 25. Reverse Nodes in k-Group

Posted on | In

Problem

Given a linked list, reverse the nodes of a linked list $k$ at a time and return its modified list.

$k$ is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of $k$ then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For $k$ = 2, you should return: 2->1->4->3->5

For $k$ = 3, you should return: 3->2->1->4->5

Note:

  • Only constant extra memory is allowed.
  • You may not alter the values in the list’s nodes, only nodes itself may be changed.

Explanation 1

  1. We want to reverse $k$ ListNode each time, and to do the reverse, we can use a $stack$ data structure because it’s last in first out.

  2. To keep track of the next $k$ ListNode, we can create a dummy node in front of the head and a pointer cur pointing to the dummy node. Then we can reference the next $k$ ListNode by using cur.next; cur = cur.next. After reversing the next $k$ node, we need to point it back to the $k+1$ node. For example, when $k$ is 3:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
           dummy->1->2->3->4->5

       Stack:

       [3]

       [2]

       [1]

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

  3. So, we need a cur pointer pointing to the dummy so we can add the nodes that are pop from the stack, and we need a nex pointer pointing to the 4, so after poping, we can link the 4 back.

Solution 1

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;
        ListNode nex = dummy.next;
        Stack<ListNode> st = new Stack<>();

        while (nex != null) {
            for (int i = 0; nex != null && i < k; i++) {
                st.push(nex);
                nex = nex.next;
            }
            if (st.size() < k) return dummy.next;
            for (int i = 0; i < k; i++) {
                cur.next = st.pop();
                cur = cur.next;
            }
            cur.next = nex;
        }

        return dummy.next;
    }
}

Explanation 2

  1. The last solution use a stack that costs $O(n)$ space. This time, we don’t need extra space. Like the last solution, we need to create a dummy node in front of the input node’s head, and need a pre pointer that points to dummy node, last pointer that points to the $k+1$’s node.

    1
    2
    3
               dummy -> 1 -> 2 -> 3 -> 4 -> 5
               |                   |
             pre                  last

  2. Now, we need to reverse the nodes between pre (exclusive) and last (exclusive), we can think of this as a sublist.

  3. We should starts from the second node in this sublist, which is node 2. We have a cur pointing to node 2 and make it become the first node. Then, cur pointing to node 3 and make node 3 pointing to the beginning of the node, and we are done reversing. Also, before we start reverse, we should have a tail node that points to 1 because it will eventually be the tail of this sublist. Finally, when cur equals to last, we are done. Before we checking the next $k$ nodes, we need to set the pre to tail and start moving the last $k$ steps next.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
               dummy -> 1 -> 2 -> 3 -> 4 -> 5
               |    |    |         |
             pre   tail  cur      last

           dummy -> 2 -> 1 -> 3 -> 4 -> 5
               |         |    |    |
             pre        tail cur  last

           dummy -> 3 -> 2 -> 1 -> 4 -> 5
               |              |    |
             pre             tail (cur)last

  4. For example, in the above second step, we want to move 2 in front of 1, we can set the nex pointer pointing to 3, then do the following:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
               dummy -> 1 -> 2 -> 3 -> 4 -> 5
               |    |    |    |    |
             pre   tail  cur  nex  last

           cur.next = pre.next
           2 -> 1 -> 2 -> 3 -> 4 -> 5

           pre.next = cur
           dummy -> 2 -> 1 -> 2 -> 3 -> 4 -> 5

           tail.next = nex
           dummy -> 2 -> 1 -> 3 -> 4 -> 5

Solution 2

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
35
36
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKNodes(ListNode pre, int k) {
        ListNode last = pre;
        for (int i = 0; i < k+1; i++) {
            last = last.next;
            if (last == null && i != k) return null;
        }
        ListNode tail = pre.next;
        ListNode cur = pre.next.next;
        while (cur != last) {
            ListNode nex = cur.next;
            cur.next = pre.next;
            pre.next = cur;
            tail.next = nex;
            cur = nex;
        }
        return tail;
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        while (pre != null) {
            pre = reverseKNodes(pre, k);
        }
        return dummy.next;
    }
}