[LeetCode 25] Reverse Nodes in k-Groups

Question

link

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

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For 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

Stats

Frequency	2
Difficulty	4
Adjusted Difficulty	4
Time to use	----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

The problem is solved in 2 steps. First, get the next k-group. If remaining items is less than k, terminate the program. Otherwise, reserve this k-group and keep going.

To solve this question is very tricky. We need to be clear about this: 4 nodes need to be kept track of: 2 elements before and after the k-group, and 2 elements within the k-group.

The difficult point is while and after reverse the k-group, how to maintain the ‘pre’ node and future ‘pre’ node correctly.

Solution

Use Linkedlist Template from NineChap to solve.

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (k <= 1 || head == null) {
            return head;
        }
        ListNode nextGroup = head;
        for (int i = 0; i < k; i++) {
            if (nextGroup == null) {
                // there isn't k nodes in this list
                return head;
            }
            nextGroup = nextGroup.next;
        }
        // now we're sure the list have at least k nodes
        // reverse this list (by re-connecting the next pointer k times)
        ListNode newHead = head;
        ListNode tail = null;
        for (int i = 0; i < k; i++) {
            ListNode temp = newHead.next;
            newHead.next = tail;
            tail = newHead;
            newHead = temp;
        }
        // now newHead is pointing to the actual new head
        // temp (which is not accessable here) is same as nextGroup
        // last step, reconnect everything and call recursion method
        head.next = reverseKGroup(nextGroup, k);
        return tail;
    }
}

Updated Oct 29, 2022

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode node = head;
    int p = 0;
    while (p < k) {
        if (node == null) break;
        node = node.next;
        p++;
    }
    if (p < k) return head;

    ListNode nextGroup = node;
    node = head;
    ListNode tail = null;
    for (int i = 0; i < k; i++) {
        ListNode temp = node.next;
        node.next = tail;
        tail = node;
        node = temp;
    }
    head.next = reverseKGroup(nextGroup, k);
    return tail;
}