Reverse Nodes in K-Group

🎯

Reverse Nodes in K-Group

hardLINKED_LISTAmazonMicrosoftGoogle

Imagine you have a playlist of songs and want to reverse every group of k songs to create a new listening experience without changing the order of the remaining songs.

💡 This problem involves manipulating linked lists in-place, which can be tricky because pointers must be carefully managed. Beginners often struggle with reversing parts of a linked list without losing track of nodes or breaking the list.

📋

Problem Statement

Given a linked list, reverse the nodes of the 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 is. You may not alter the values in the nodes, only nodes themselves may be changed.

The number of nodes in the list is n1 ≤ n ≤ 10^51 ≤ k ≤ n

💡

Example

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

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

The list is reversed in groups of 2. The first two nodes (1,2) are reversed to (2,1), the next two nodes (3,4) reversed to (4,3), and the last node (5) remains as is.

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

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

The first three nodes are reversed (1,2,3) → (3,2,1), the remaining nodes (4,5) are less than k so remain unchanged.

• k = 1 → list remains unchanged
• k equals list length → entire list reversed
• List length is not a multiple of k → last nodes remain as is
• List with only one node → no change regardless of k

⚠️

Common Mistakes

Not checking if there are at least k nodes before reversal

Leads to partial reversal of fewer than k nodes, violating problem constraints

✅ Always count k nodes ahead before reversing

Losing track of the next group's head after reversal

The list becomes disconnected or forms cycles

✅ Store the node after the kth node before reversal and reconnect after reversal

Incorrectly updating the previous group's tail pointer

Subsequent groups are not connected properly, resulting in broken list

✅ After reversal, update the previous group's next pointer to the new head and move the previous pointer to the tail

Using recursion without considering stack overflow for large lists

Program crashes or times out on large inputs

✅ Use iterative approach for large inputs to avoid deep recursion

🧠

Brute Force (Recursive Reversal with Counting)

💡 This approach uses recursion to reverse the first k nodes and then recursively processes the rest. It is straightforward but can be inefficient and risks stack overflow for large lists.

Intuition

Reverse the first k nodes by recursion, then attach the reversed part to the result of recursively reversing the remaining list.

Algorithm

1. Check if there are at least k nodes to reverse; if not, return head as is.
2. Reverse the first k nodes recursively.
3. Recursively call the function on the remaining list after the first k nodes.
4. Connect the reversed first k nodes to the result of the recursive call.

💡 The recursion and pointer manipulation can be confusing at first because you must carefully track the head and tail of reversed segments.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseKGroup(head, k):
    count = 0
    ptr = head
    # Check if there are at least k nodes
    while ptr and count < k:
        ptr = ptr.next
        count += 1
    if count < k:
        return head
    # Reverse first k nodes
    prev = None
    curr = head
    for _ in range(k):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # Recursively call for the rest of the list
    head.next = reverseKGroup(curr, k)
    return prev

# Driver code to test
if __name__ == '__main__':
    # Create linked list 1->2->3->4->5
    nodes = [ListNode(i) for i in range(1, 6)]
    for i in range(4):
        nodes[i].next = nodes[i+1]
    new_head = reverseKGroup(nodes[0], 2)
    # Print reversed list
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next

Line Notes

while ptr and count < k:Check if there are at least k nodes to reverse

if count < k:If fewer than k nodes remain, return head unchanged

for _ in range(k):Reverse exactly k nodes iteratively

head.next = reverseKGroup(curr, k)Connect reversed segment to recursively processed remainder

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int count = 0;
        ListNode ptr = head;
        // Check if there are at least k nodes
        while (ptr != null && count < k) {
            ptr = ptr.next;
            count++;
        }
        if (count < k) return head;
        // Reverse first k nodes
        ListNode prev = null;
        ListNode curr = head;
        for (int i = 0; i < k; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        // Recursively call for the rest
        head.next = reverseKGroup(curr, k);
        return prev;
    }

    public static void main(String[] args) {
        ListNode[] nodes = new ListNode[5];
        for (int i = 0; i < 5; i++) nodes[i] = new ListNode(i + 1);
        for (int i = 0; i < 4; i++) nodes[i].next = nodes[i + 1];
        Solution sol = new Solution();
        ListNode newHead = sol.reverseKGroup(nodes[0], 2);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
    }
}

Line Notes

while (ptr != null && count < k)Verify at least k nodes exist before reversal

if (count < k) return head;Return original head if fewer than k nodes remain

for (int i = 0; i < k; i++)Reverse k nodes iteratively

head.next = reverseKGroup(curr, k);Link reversed segment to recursive result

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int count = 0;
        ListNode* ptr = head;
        // Check if there are at least k nodes
        while (ptr && count < k) {
            ptr = ptr->next;
            count++;
        }
        if (count < k) return head;
        // Reverse first k nodes
        ListNode* prev = nullptr;
        ListNode* curr = head;
        for (int i = 0; i < k; i++) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        // Recursively call for the rest
        head->next = reverseKGroup(curr, k);
        return prev;
    }
};

int main() {
    ListNode* nodes[5];
    for (int i = 0; i < 5; i++) nodes[i] = new ListNode(i + 1);
    for (int i = 0; i < 4; i++) nodes[i]->next = nodes[i + 1];
    Solution sol;
    ListNode* newHead = sol.reverseKGroup(nodes[0], 2);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

while (ptr && count < k)Ensure at least k nodes exist before reversal

if (count < k) return head;Return original list if fewer than k nodes remain

for (int i = 0; i < k; i++)Reverse k nodes iteratively using pointers

head->next = reverseKGroup(curr, k);Connect reversed segment to recursive call result

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function reverseKGroup(head, k) {
    let count = 0;
    let ptr = head;
    // Check if there are at least k nodes
    while (ptr !== null && count < k) {
        ptr = ptr.next;
        count++;
    }
    if (count < k) return head;
    // Reverse first k nodes
    let prev = null;
    let curr = head;
    for (let i = 0; i < k; i++) {
        let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    // Recursively call for the rest
    head.next = reverseKGroup(curr, k);
    return prev;
}

// Driver code
const nodes = [1,2,3,4,5].map(v => new ListNode(v));
for (let i = 0; i < nodes.length - 1; i++) nodes[i].next = nodes[i+1];
const newHead = reverseKGroup(nodes[0], 2);
let curr = newHead;
while (curr) {
    console.log(curr.val);
    curr = curr.next;
}

Line Notes

while (ptr !== null && count < k)Verify existence of k nodes before reversal

if (count < k) return head;Return original head if fewer than k nodes remain

for (let i = 0; i < k; i++)Reverse k nodes iteratively by pointer manipulation

head.next = reverseKGroup(curr, k);Attach reversed segment to recursive call result

⏱

Complexity

TimeO(n)

SpaceO(n/k) due to recursion stack

Each node is visited once, but recursion depth is n/k because each call processes k nodes. Hence time is linear, space is linear in number of groups.

💡 For n=20 and k=2, about 10 recursive calls happen, which is manageable but can cause stack overflow for very large n.

Interview Verdict: Accepted but not optimal for very large lists due to recursion depth

This approach is good to understand the problem but may fail in interviews if the list is very large due to stack overflow risk.

🧠

Iterative Approach with Dummy Node and In-Place Reversal

💡 This approach avoids recursion by using a dummy node and iteratively reversing k nodes at a time, which is more efficient and safer for large inputs.

Intuition

Use a dummy node to simplify edge cases, count k nodes ahead, then reverse the k nodes in-place by adjusting pointers iteratively.

Algorithm

1. Create a dummy node pointing to head to handle edge cases.
2. Use a pointer to check if there are at least k nodes ahead.
3. If yes, reverse the k nodes by changing pointers in-place.
4. Move the pointer forward and repeat until fewer than k nodes remain.

💡 The pointer manipulations can be tricky, especially maintaining connections before and after the reversed segment.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseKGroup(head, k):
    dummy = ListNode(0)
    dummy.next = head
    group_prev = dummy

    while True:
        kth = group_prev
        count = 0
        # Find the kth node
        while kth.next and count < k:
            kth = kth.next
            count += 1
        if count < k:
            break
        group_next = kth.next
        # Reverse group
        prev, curr = group_next, group_prev.next
        for _ in range(k):
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        tmp = group_prev.next
        group_prev.next = prev
        group_prev = tmp
    return dummy.next

# Driver code
if __name__ == '__main__':
    nodes = [ListNode(i) for i in range(1, 6)]
    for i in range(4):
        nodes[i].next = nodes[i+1]
    new_head = reverseKGroup(nodes[0], 2)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next

Line Notes

dummy = ListNode(0)Create dummy node to simplify head manipulations

while kth.next and count < k:Find kth node to determine if reversal is possible

prev, curr = group_next, group_prev.nextInitialize pointers for reversal with prev starting at node after group

group_prev.next = prevConnect previous group's tail to new head after reversal

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode groupPrev = dummy;

        while (true) {
            ListNode kth = groupPrev;
            int count = 0;
            while (kth.next != null && count < k) {
                kth = kth.next;
                count++;
            }
            if (count < k) break;
            ListNode groupNext = kth.next;
            ListNode prev = groupNext;
            ListNode curr = groupPrev.next;
            for (int i = 0; i < k; i++) {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            ListNode tmp = groupPrev.next;
            groupPrev.next = prev;
            groupPrev = tmp;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode[] nodes = new ListNode[5];
        for (int i = 0; i < 5; i++) nodes[i] = new ListNode(i + 1);
        for (int i = 0; i < 4; i++) nodes[i].next = nodes[i + 1];
        Solution sol = new Solution();
        ListNode newHead = sol.reverseKGroup(nodes[0], 2);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
    }
}

Line Notes

ListNode dummy = new ListNode(0);Dummy node simplifies edge case handling

while (kth.next != null && count < k)Locate kth node to check if reversal is possible

curr.next = prev;Reverse pointers within the group

groupPrev.next = prev;Connect previous group's tail to new head after reversal

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* groupPrev = &dummy;

        while (true) {
            ListNode* kth = groupPrev;
            int count = 0;
            while (kth->next && count < k) {
                kth = kth->next;
                count++;
            }
            if (count < k) break;
            ListNode* groupNext = kth->next;
            ListNode* prev = groupNext;
            ListNode* curr = groupPrev->next;
            for (int i = 0; i < k; i++) {
                ListNode* next = curr->next;
                curr->next = prev;
                prev = curr;
                curr = next;
            }
            ListNode* tmp = groupPrev->next;
            groupPrev->next = prev;
            groupPrev = tmp;
        }
        return dummy.next;
    }
};

int main() {
    ListNode* nodes[5];
    for (int i = 0; i < 5; i++) nodes[i] = new ListNode(i + 1);
    for (int i = 0; i < 4; i++) nodes[i]->next = nodes[i + 1];
    Solution sol;
    ListNode* newHead = sol.reverseKGroup(nodes[0], 2);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

ListNode dummy(0);Dummy node to handle edge cases uniformly

while (kth->next && count < k)Find kth node to confirm group size

curr->next = prev;Reverse pointers within the group

groupPrev->next = prev;Connect previous group's tail to new head after reversal

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function reverseKGroup(head, k) {
    const dummy = new ListNode(0);
    dummy.next = head;
    let groupPrev = dummy;

    while (true) {
        let kth = groupPrev;
        let count = 0;
        while (kth.next !== null && count < k) {
            kth = kth.next;
            count++;
        }
        if (count < k) break;
        const groupNext = kth.next;
        let prev = groupNext;
        let curr = groupPrev.next;
        for (let i = 0; i < k; i++) {
            const next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        const tmp = groupPrev.next;
        groupPrev.next = prev;
        groupPrev = tmp;
    }
    return dummy.next;
}

// Driver code
const nodes = [1,2,3,4,5].map(v => new ListNode(v));
for (let i = 0; i < nodes.length - 1; i++) nodes[i].next = nodes[i+1];
const newHead = reverseKGroup(nodes[0], 2);
let curr = newHead;
while (curr) {
    console.log(curr.val);
    curr = curr.next;
}

Line Notes

const dummy = new ListNode(0);Dummy node simplifies edge cases

while (kth.next !== null && count < k)Find kth node to check group size

curr.next = prev;Reverse pointers within the group

groupPrev.next = prev;Connect previous group's tail to new head after reversal

⏱

Complexity

TimeO(n)

SpaceO(1)

Each node is visited once and reversed in-place without recursion, so time is linear and space is constant.

💡 For n=20 and k=2, about 10 groups are reversed iteratively, which is efficient and safe for large inputs.

Interview Verdict: Accepted and optimal for large inputs

This is the preferred approach in interviews because it is efficient and avoids recursion stack issues.

🧠

Iterative Approach with Helper Function for Reversal

💡 This approach modularizes the reversal logic into a helper function to improve code clarity and reuse, while still performing in-place iterative reversal.

Intuition

Separate the reversal of k nodes into a helper function, then use a loop to process the entire list group by group.

Algorithm

1. Create a dummy node pointing to head.
2. Iterate through the list, checking if k nodes remain.
3. Call a helper function to reverse k nodes and return new head and tail.
4. Connect reversed group to previous part and continue until fewer than k nodes remain.

💡 Breaking down reversal into a helper function makes the main logic easier to follow but requires careful pointer management.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseLinkedList(head, k):
    prev = None
    curr = head
    while k > 0:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
        k -= 1
    return prev

def reverseKGroup(head, k):
    dummy = ListNode(0)
    dummy.next = head
    group_prev = dummy

    while True:
        kth = group_prev
        count = 0
        while kth.next and count < k:
            kth = kth.next
            count += 1
        if count < k:
            break
        group_next = kth.next
        # Reverse k nodes
        prev = reverseLinkedList(group_prev.next, k)
        tail = group_prev.next
        tail.next = group_next
        group_prev.next = prev
        group_prev = tail
    return dummy.next

# Driver code
if __name__ == '__main__':
    nodes = [ListNode(i) for i in range(1, 6)]
    for i in range(4):
        nodes[i].next = nodes[i+1]
    new_head = reverseKGroup(nodes[0], 2)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next

Line Notes

def reverseLinkedList(head, k):Helper function to reverse exactly k nodes

while kth.next and count < k:Check if k nodes exist before reversal

prev = reverseLinkedList(group_prev.next, k)Reverse k nodes using helper

group_prev.next = prevConnect previous group's tail to reversed head

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    private ListNode reverseLinkedList(ListNode head, int k) {
        ListNode prev = null;
        ListNode curr = head;
        while (k > 0) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
            k--;
        }
        return prev;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode groupPrev = dummy;

        while (true) {
            ListNode kth = groupPrev;
            int count = 0;
            while (kth.next != null && count < k) {
                kth = kth.next;
                count++;
            }
            if (count < k) break;
            ListNode groupNext = kth.next;
            ListNode prev = reverseLinkedList(groupPrev.next, k);
            ListNode tail = groupPrev.next;
            tail.next = groupNext;
            groupPrev.next = prev;
            groupPrev = tail;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode[] nodes = new ListNode[5];
        for (int i = 0; i < 5; i++) nodes[i] = new ListNode(i + 1);
        for (int i = 0; i < 4; i++) nodes[i].next = nodes[i + 1];
        Solution sol = new Solution();
        ListNode newHead = sol.reverseKGroup(nodes[0], 2);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
    }
}

Line Notes

private ListNode reverseLinkedList(ListNode head, int k)Helper method to reverse k nodes

while (kth.next != null && count < k)Check if k nodes exist before reversal

ListNode prev = reverseLinkedList(groupPrev.next, k);Reverse k nodes using helper

groupPrev.next = prev;Connect previous group's tail to reversed head

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* reverseLinkedList(ListNode* head, int k) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (k > 0) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
            k--;
        }
        return prev;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* groupPrev = &dummy;

        while (true) {
            ListNode* kth = groupPrev;
            int count = 0;
            while (kth->next && count < k) {
                kth = kth->next;
                count++;
            }
            if (count < k) break;
            ListNode* groupNext = kth->next;
            ListNode* prev = reverseLinkedList(groupPrev->next, k);
            ListNode* tail = groupPrev->next;
            tail->next = groupNext;
            groupPrev->next = prev;
            groupPrev = tail;
        }
        return dummy.next;
    }
};

int main() {
    ListNode* nodes[5];
    for (int i = 0; i < 5; i++) nodes[i] = new ListNode(i + 1);
    for (int i = 0; i < 4; i++) nodes[i]->next = nodes[i + 1];
    Solution sol;
    ListNode* newHead = sol.reverseKGroup(nodes[0], 2);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

ListNode* reverseLinkedList(ListNode* head, int k)Helper function to reverse k nodes

while (kth->next && count < k)Check if k nodes exist before reversal

ListNode* prev = reverseLinkedList(groupPrev->next, k);Reverse k nodes using helper

groupPrev->next = prev;Connect previous group's tail to reversed head

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function reverseLinkedList(head, k) {
    let prev = null;
    let curr = head;
    while (k > 0) {
        let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
        k--;
    }
    return prev;
}

function reverseKGroup(head, k) {
    const dummy = new ListNode(0);
    dummy.next = head;
    let groupPrev = dummy;

    while (true) {
        let kth = groupPrev;
        let count = 0;
        while (kth.next !== null && count < k) {
            kth = kth.next;
            count++;
        }
        if (count < k) break;
        const groupNext = kth.next;
        const prev = reverseLinkedList(groupPrev.next, k);
        const tail = groupPrev.next;
        tail.next = groupNext;
        groupPrev.next = prev;
        groupPrev = tail;
    }
    return dummy.next;
}

// Driver code
const nodes = [1,2,3,4,5].map(v => new ListNode(v));
for (let i = 0; i < nodes.length - 1; i++) nodes[i].next = nodes[i+1];
const newHead = reverseKGroup(nodes[0], 2);
let curr = newHead;
while (curr) {
    console.log(curr.val);
    curr = curr.next;
}

Line Notes

function reverseLinkedList(head, k)Helper function to reverse k nodes

while (kth.next !== null && count < k)Check if k nodes exist before reversal

const prev = reverseLinkedList(groupPrev.next, k);Reverse k nodes using helper

groupPrev.next = prev;Connect previous group's tail to reversed head

⏱

Complexity

TimeO(n)

SpaceO(1)

Each node is visited once and reversed in-place using the helper function, so time is linear and space is constant.

💡 This approach is as efficient as the previous iterative one but improves code readability.

Interview Verdict: Accepted and optimal with modular code

This approach is ideal for interviews where clean, modular code is valued alongside efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the iterative approach with a dummy node is preferred because it is efficient and safe. The recursive approach is good for understanding but risky for large inputs.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive)	O(n)	O(n/k) recursion stack	Yes (deep recursion)	N/A	Mention only - never code for large inputs
2. Iterative with Dummy Node	O(n)	O(1)	No	N/A	Code this approach in 95% of interviews
3. Iterative with Helper Function	O(n)	O(1)	No	N/A	Good for clean modular code, also optimal

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show your understanding, and finally present the optimal iterative solution. Practice coding and testing edge cases.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force recursive approach to demonstrate understanding.Step 3: Explain the iterative approach with a dummy node for efficiency.Step 4: Code the iterative solution carefully, explaining pointer manipulations.Step 5: Test your code with edge cases and explain your reasoning.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 12min → Test: 5min. Total ~25min

What the Interviewer Tests

The interviewer tests your understanding of linked list pointer manipulations, ability to handle edge cases, and efficiency in reversing nodes in groups without extra space.

Common Follow-ups

• What if k is 1? → The list remains unchanged.
• Can you reverse nodes in groups of varying sizes? → Requires modifying the logic to handle dynamic group sizes.

💡 These follow-ups test your ability to adapt the solution to edge cases and variations, which is common in interviews.

🔍

Pattern Recognition

When to Use

1) You need to reverse nodes in a linked list in groups; 2) The group size k is given; 3) Partial groups at the end remain unchanged; 4) In-place reversal is required.

Signature Phrases

reverse nodes k at a timeif number of nodes is not multiple of k, leave as is

NOT This Pattern When

Reversing entire list without grouping or reversing based on values (not groups) is a different pattern.

Similar Problems

Reverse Linked List - simpler reversal of entire listSwap Nodes in Pairs - special case of k=2 reversal

Practice

1. You are given k sorted linked lists and need to merge them into one sorted linked list efficiently. Which approach guarantees the optimal time complexity for this problem?

easy

A. Merge all lists into one array, then sort the array and rebuild the linked list.

B. Use dynamic programming to store intermediate merged results and avoid repeated merges.

C. Use a min-heap (priority queue) to repeatedly extract the smallest node among the heads of the lists.

D. Merge the lists one by one sequentially, merging two lists at a time from left to right.

Solution

1. Step 1: Understand problem constraints

   We have k sorted linked lists and want to merge them efficiently.

2. Step 2: Compare approaches

   Brute force sorting all nodes is O(N log N). Sequential merges cost O(kN). Min-heap approach extracts smallest node in O(log k) time, total O(N log k), which is optimal.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Min-heap approach uses priority queue to achieve O(N log k) [OK]

Hint: Min-heap merges k lists in O(N log k) time [OK]

Common Mistakes:

• Thinking sequential merges are optimal
• Assuming sorting all nodes is best
• Confusing DP with merge approach

2. Consider the following code snippet implementing the merge function used in bottom-up merge sort on linked lists. Given two sorted linked lists l1 and l2 with values l1: 1 -> 4 and l2: 2 -> 3, what is the resulting merged list after calling merge(l1, l2)?

easy

A. 1 -> 2 -> 4 -> 3

B. 1 -> 2 -> 3 -> 4

C. 2 -> 3 -> 1 -> 4

D. 1 -> 4 -> 2 -> 3

Solution

1. Step 1: Compare first nodes of l1 and l2

   l1.val=1, l2.val=2, 1 < 2, so add 1 to merged list and move l1 forward.

2. Step 2: Continue merging remaining nodes

   Now l1.val=4, l2.val=2, 2 < 4, add 2, move l2 forward; then 3 < 4, add 3, move l2 forward; l2 is null, append remaining l1 node 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Result is sorted merged list 1 -> 2 -> 3 -> 4 [OK]

Hint: Merge picks smaller node each step, preserving order [OK]

Common Mistakes:

• Appending entire l2 before l1 without comparison
• Not updating tail pointer correctly
• Confusing order of nodes after merge

3. Identify the bug in the following code snippet that attempts to delete a node from a singly linked list given only access to that node.

def deleteNode(node):
    node.val = node.next.val
    # Missing update of next pointer

What is the consequence of this bug?

medium

A. The list will contain duplicate values and the node is not truly deleted.

B. The node is correctly deleted with no issues.

C. The code will raise a runtime error due to null pointer dereference.

D. The node will be set to None, breaking the list.

Solution

1. Step 1: Analyze the code's effect

   Only the node's value is overwritten with the next node's value, but the next pointer is not updated.

2. Step 2: Understand the consequence

   Since next pointer is unchanged, the next node remains in the list, causing duplicate values and no actual deletion.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Next pointer must be updated to remove next node [OK]

Hint: Must update next pointer after copying value [OK]

Common Mistakes:

• Forgetting to update next pointer after copying value
• Assuming setting node to None deletes it
• Trying to delete tail node with this method

4. Identify the bug in the following code snippet intended to find the intersection node of two singly linked lists using the two-pointer approach:

medium

A. Line 6: Using '!=' instead of 'is not' to compare nodes

B. Line 8: Not checking if headA or headB is None before starting

C. Line 9: Incorrectly resetting pA and pB to headB and headA respectively

D. Line 10: Returning pA instead of pB

Solution

1. Step 1: Understand node comparison

   Nodes must be compared by reference, not by value. Using '!=' compares values, not references, causing incorrect intersection detection.

2. Step 2: Identify correct comparison operator

   'is not' compares object identity, ensuring correct detection of intersection node.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using '!=' causes false positives or misses intersection [OK]

Hint: Use 'is' or 'is not' to compare nodes, not '==' or '!=' [OK]

Common Mistakes:

• Comparing node values instead of references
• Forgetting to handle empty lists
• Infinite loops due to pointer reset errors

5. The following code attempts to rotate a linked list to the right by k places. Identify the line that contains a subtle bug that can cause the list to become cyclic or truncated incorrectly.

medium

A. Line: tail.next = head # make circular

B. Line: slow.next = slow # BUG: incorrect break causing cycle

C. Line: for _ in range(k): fast = fast.next

D. Line: k = k % length

Solution

1. Step 1: Understand the purpose of breaking the list

   After rotation, the list must be broken at the new tail by setting slow.next = None.

2. Step 2: Identify the bug

   The original code sets slow.next = slow, which creates a cycle instead of breaking the list.

3. Step 3: Correct fix

   Change to slow.next = None to properly break the list.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Correct break is slow.next = None [OK]

Hint: Break list by setting slow.next = None [OK]

Common Mistakes:

• Setting slow.next to itself or wrong node causing cycles
• Not handling k modulo length correctly
• Forgetting to make list circular before rotation