Reverse Nodes in k-Group

HARD

Description

Given the head of a linked list, reverse the nodes of the list k at a time, and return the 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.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Example 2:

Input: head = [1,2,3,4,5], k = 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: Can you solve the problem in O(1) extra memory space?

Approaches

Checkout 3 different approaches to solve Reverse Nodes in k-Group. Click on different approaches to view the approach and algorithm in detail.

Stack-Based Approach

This approach uses a stack to reverse nodes in groups of k. We iterate through the linked list, and for each group of k nodes, we push them onto a stack. Then, we pop the nodes from the stack and relink them in reversed order. This process is repeated until the end of the list is reached. If the last group has fewer than k nodes, it is left unchanged.

Algorithm

Create a dummy node pointing to head and a prev pointer to dummy.
Create a stack to store nodes.
Loop through the list:
- First, check if there are k nodes available starting from prev.next.
- If not, break the loop.
- If yes, push the k nodes onto the stack.
- Pop nodes from the stack and relink them. prev.next will point to the first popped node. Update prev after each pop.
- After the group is reversed, link the tail of the reversed group to the start of the next group.
Return dummy.next.

This method provides a straightforward way to reverse the groups by leveraging the Last-In, First-Out (LIFO) property of a stack.

Algorithm:

Create a dummy node that points to the head of the list. This simplifies handling the list's head.
Initialize a p pointer to the dummy node. This pointer will track the end of the previously reversed group.
Use a while loop to traverse the list. In each iteration, we first check if there are at least k nodes remaining.
If a group of k nodes exists, push these k nodes onto a stack.
Pop the nodes from the stack one by one and link them back into the list starting from p.next. Update p to point to the last node of the newly reversed group.
The next of the new tail of the group should point to the start of the next group.
If fewer than k nodes remain, the check at the beginning of the loop will fail, and we return the result.
Return dummy.next.

import java.util.Stack;

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;

        Stack<ListNode> stack = new Stack<>();
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p = dummy;

        while (true) {
            ListNode check = p.next;
            int i = 0;
            for (; i < k; i++) {
                if (check == null) break;
                check = check.next;
            }
            if (i < k) break; // Not enough nodes

            ListNode temp = p.next;
            for (i = 0; i < k; i++) {
                stack.push(temp);
                temp = temp.next;
            }

            while (!stack.isEmpty()) {
                p.next = stack.pop();
                p = p.next;
            }
            p.next = temp;
        }
        return dummy.next;
    }
}

Complexity Analysis

Time Complexity: O(N)Space Complexity: O(k)

Pros and Cons

Pros:

Conceptually simple and easy to understand.
Leverages a standard data structure.

Cons:

Uses O(k) extra space, which is not optimal and fails the follow-up constraint.

Code Solutions

Checking out 4 solutions in different languages for Reverse Nodes in k-Group. Click on different languages to view the code.

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode ReverseKGroup ( ListNode head , int k ) { ListNode dummy = new ListNode ( 0 , head ); ListNode pre = dummy , cur = dummy ; while ( cur . next != null ) { for ( int i = 0 ; i < k && cur != null ; ++ i ) { cur = cur . next ; } if ( cur == null ) { return dummy . next ; } ListNode t = cur . next ; cur . next = null ; ListNode start = pre . next ; pre . next = ReverseList ( start ); start . next = t ; pre = start ; cur = pre ; } return dummy . next ; } private ListNode ReverseList ( ListNode head ) { ListNode pre = null , p = head ; while ( p != null ) { ListNode q = p . next ; p . next = pre ; pre = p ; p = q ; } return pre ; } }

Video Solution

Watch the video walkthrough for Reverse Nodes in k-Group

Patterns:

Recursion

Data Structures:

Linked List

Companies:

Adobe |Amazon |Apple |Bloomberg |