LeetCode Problem

Problem Description

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

Examples

Input: [1,2,3,4,5], 2
Output: [2,1,4,3,5]

Input: [1,2,3,4,5], 3
Output: [3,2,1,4,5]

Constraints

The number of nodes in the list is n.
1 <= k <= n <= 5000
0 <= Node.val <= 1000

Follow-up

Approach to Solve

Use a dummy node to simplify the process of reversing k groups.

Code Implementation

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        groupPrev = dummy
        while True:
            kth = self.getKth(groupPrev, k)
            if not kth:
                break
            groupNext = kth.next
            prev, curr = kth.next, groupPrev.next
            while curr != groupNext:
                temp = curr.next
                curr.next = prev
                prev = curr
                curr = temp
            temp = groupPrev.next
            groupPrev.next = kth
            groupPrev = temp
        return dummy.next

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode groupPrev = dummy;
        while (true) {
            ListNode kth = getKth(groupPrev, k);
            if (kth == null) break;
            ListNode groupNext = kth.next;
            ListNode prev = kth.next, curr = groupPrev.next;
            while (curr != groupNext) {
                ListNode temp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = temp;
            }
            ListNode temp = groupPrev.next;
            groupPrev.next = kth;
            groupPrev = temp;
        }
        return dummy.next;
    }
    private ListNode getKth(ListNode curr, int k) {
        while (curr != null && k > 0) {
            curr = curr.next;
k--;
        }
        return curr;
    }

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* groupPrev = dummy;
        while (true) {
            ListNode* kth = getKth(groupPrev, k);
            if (kth == nullptr) break;
            ListNode* groupNext = kth->next;
            ListNode* prev = kth->next, *curr = groupPrev->next;
            while (curr != groupNext) {
                ListNode* temp = curr->next;
                curr->next = prev;
                prev = curr;
                curr = temp;
            }
            ListNode* temp = groupPrev->next;
            groupPrev->next = kth;
            groupPrev = temp;
        }
        return dummy->next;
    }
    ListNode* getKth(ListNode* curr, int k) {
        while (curr != nullptr && k > 0) {
            curr = curr->next;
k--;
        }
        return curr;
    }

Explanation

This solution uses a dummy node to simplify the process of reversing k groups. Here's a detailed explanation of the algorithm:

Create a dummy node: We start by creating a dummy node with a value of 0 and set its next pointer to the head of the input list. This helps handle edge cases, such as when the list has fewer than k nodes.
Initialize a groupPrev pointer: We use a 'groupPrev' pointer to keep track of the previous node of the current group. Initially, it points to the dummy node.
Iterate through the list: We continue this process while the current group has k nodes.
Reverse the current group:
- Find the kth node of the current group using the getKth function.
- Store the next node of the kth node as groupNext.
- Use two pointers (prev and curr) to reverse the current group.
- Update the pointers to move forward in the list.
Update the groupPrev pointer:
- After reversing the current group, update groupPrev to point to the last node of the reversed group.
Return the modified list: After the loop, we return the next node of the dummy node, which is the head of our modified list.

The getKth function is used to find the kth node of the current group. This ensures that we can reverse the group correctly and handle cases where the list does not have a multiple of k nodes.

Time Complexity: O(n), where n is the number of nodes in the list. Each node is processed once during the reversal process. Space Complexity: O(1), as we only use a constant amount of extra space for the dummy node and pointers.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

LeetSolved

Reverse Nodes in k-Group