Bird
Raised Fist0
Interview Preplinked-list-advancedhardAmazonMicrosoftGoogleFacebook

Reverse Linked List in Groups of K (Generalization)

Choose your preparation mode4 modes available
🎯
Reverse Linked List in Groups of K (Generalization)
hardLINKED_LISTAmazonMicrosoftGoogle

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

💡 This problem is about manipulating linked lists in chunks rather than all at once. Beginners often struggle because it requires careful pointer management and understanding how to reverse sublists and reconnect them properly.
📋
Problem Statement

Given a singly 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.

1 ≤ n ≤ 10^5 (number of nodes in the linked list)1 ≤ k ≤ nNode values can be any integerYou must solve the problem in O(n) time and O(1) extra space
💡
Example
Input"head = [1,2,3,4,5], k = 2"
Output[2,1,4,3,5]

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

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

First three nodes reversed (1,2,3) → (3,2,1), last two nodes remain as is because less than k.

  • k = 1 → list remains unchanged
  • k equals list length → entire list reversed
  • List length not multiple of k → last nodes remain in original order
  • Empty list (head = null) → return null
⚠️
Common Mistakes
Not checking if there are at least k nodes before reversing

Partial groups get reversed incorrectly, leading to wrong output

✅ Always check if k nodes exist before reversal

Losing track of next group's start during reversal

List gets disconnected or forms cycles causing runtime errors

✅ Store next group's start before reversal and reconnect after

Incorrectly updating the previous group's tail pointer after reversal

Subsequent groups are not connected properly, resulting in truncated list

✅ Update group_prev pointer to the tail of the reversed group after each reversal

Using recursion without considering stack overflow for large lists

Stack overflow or timeout in large inputs

✅ Use iterative approach for large inputs to avoid recursion overhead

🧠
Brute Force (Recursive Reversal with Length Check)
💡 This approach uses recursion to reverse the first k nodes and then recursively processes the rest. It helps beginners understand the problem by breaking it down into smaller subproblems but is not optimal due to recursion overhead.

Intuition

Reverse the first k nodes recursively, then connect the reversed part with 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 using recursion.
  3. Recursively call the function on the remaining list after the first k nodes.
  4. Connect the reversed k nodes with the result of the recursive call.
💡 The challenge is to correctly reverse k nodes and then link them to the recursively processed remainder, which requires careful pointer handling.
</>
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
    # head is now the tail of reversed group
    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, return head as is (no reversal)
for _ in range(k):Reverse exactly k nodes iteratively
head.next = reverseKGroup(curr, k)Connect reversed group to recursively processed remainder
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

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;
        }
        // head is now tail of reversed group
        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 not enough nodes
for (int i = 0; i < k; i++)Reverse k nodes iteratively
head.next = reverseKGroup(curr, k);Recursively connect reversed group to remainder
#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 != nullptr && 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;
        }
        // head is now tail of reversed group
        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 != nullptr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}
Line Notes
while (ptr != nullptr && count < k)Ensure at least k nodes exist before reversal
if (count < k) return head;Return original list if fewer than k nodes
for (int i = 0; i < k; i++)Reverse k nodes iteratively
head->next = reverseKGroup(curr, k);Recursively connect reversed group to remainder
class ListNode {
    constructor(val = 0, 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;
    }
    // head is now tail of reversed group
    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;
let output = [];
while (curr !== null) {
    output.push(curr.val);
    curr = curr.next;
}
console.log(output.join(' '));
Line Notes
while (ptr !== null && count < k)Check if enough nodes exist to reverse
if (count < k) return head;Return original head if less than k nodes
for (let i = 0; i < k; i++)Reverse k nodes iteratively
head.next = reverseKGroup(curr, k);Recursively connect reversed group to remainder
⏱
Complexity
TimeO(n)
SpaceO(n/k) due to recursion stack

Each node is visited once, but recursion depth is n/k because each recursive call processes k nodes. So time is linear, space is linear in worst case due to recursion.

💡 For n=20 and k=2, recursion depth is 10, so 10 recursive calls and 20 node visits.
Interview Verdict: Accepted but not optimal due to recursion stack

This approach works but can cause stack overflow for very large lists; good for understanding but not always practical.

🧠
Iterative Approach with Dummy Node and Pointer Manipulation
💡 This approach avoids recursion by iteratively reversing k nodes using pointer manipulation and a dummy node to simplify edge cases. It is more efficient and preferred in interviews.

Intuition

Use a dummy node to handle head changes, then iteratively reverse each group of k nodes by adjusting pointers carefully.

Algorithm

  1. Create a dummy node pointing to head to simplify edge cases.
  2. Use pointers to check if there are k nodes ahead to reverse.
  3. Reverse the k nodes by changing next pointers iteratively.
  4. Move pointers forward and repeat until the end of the list.
💡 The key difficulty is managing multiple pointers to reverse sublists and reconnect them without losing track of nodes.
</>
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
        # Find the kth node
        count = 0
        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)Dummy node simplifies handling head changes
while True:Loop until no more k-sized groups to reverse
while kth.next and count < k:Find kth node to check if group is complete
for _ in range(k):Reverse k nodes by pointer manipulation
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

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 to handle head changes cleanly
while (true) {Process all k-sized groups iteratively
while (kth.next != null && count < k)Check if enough nodes remain to reverse
for (int i = 0; i < k; i++)Reverse k nodes by changing pointers
#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 != nullptr && 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 != nullptr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}
Line Notes
ListNode dummy(0);Dummy node to simplify head handling
while (true) {Iterate over all groups until no more full groups
while (kth->next != nullptr && count < k)Check if group has k nodes
for (int i = 0; i < k; i++)Reverse k nodes by pointer manipulation
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function reverseKGroup(head, k) {
    const dummy = new ListNode(0, 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;
const output = [];
while (curr !== null) {
    output.push(curr.val);
    curr = curr.next;
}
console.log(output.join(' '));
Line Notes
const dummy = new ListNode(0, head);Dummy node to handle head changes easily
while (true) {Process all groups iteratively
while (kth.next !== null && count < k)Check if group has k nodes
for (let i = 0; i < k; i++)Reverse k nodes by pointer manipulation
⏱
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, the algorithm does about 20 node visits and pointer changes with no extra memory.
Interview Verdict: Accepted and optimal for interviews

This is the preferred approach in interviews due to its efficiency and no recursion overhead.

🧠
Iterative Approach with Helper Function to Reverse Sublist
💡 This approach modularizes the reversal logic by using a helper function to reverse a sublist between two pointers, improving code readability and maintainability.

Intuition

Split the problem into two parts: a helper to reverse a sublist, and the main function to iterate over the list and reverse groups using the helper.

Algorithm

  1. Create a dummy node pointing to head.
  2. Iterate through the list to find groups of k nodes.
  3. Use a helper function to reverse the nodes between group boundaries.
  4. Reconnect the reversed group and move to the next group.
💡 Separating reversal logic into a helper clarifies the main loop and reduces complexity in pointer management.
</>
Code
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseBetween(start, end):
    prev = None
    curr = start
    while curr != end:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    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 group
        prev = reverseBetween(group_prev.next, group_next)

        tmp = group_prev.next
        group_prev.next = prev
        tmp.next = group_next
        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
def reverseBetween(start, end):Helper reverses nodes from start up to but not including end
while curr != end:Reverse nodes until reaching end boundary
group_next = kth.nextStore next group's start before reversal
tmp.next = group_nextReconnect reversed group to next part of list
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class Solution {
    private ListNode reverseBetween(ListNode start, ListNode end) {
        ListNode prev = null;
        ListNode curr = start;
        while (curr != end) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        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 = reverseBetween(groupPrev.next, groupNext);

            ListNode tmp = groupPrev.next;
            groupPrev.next = prev;
            tmp.next = groupNext;
            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
private ListNode reverseBetween(ListNode start, ListNode end)Helper reverses nodes from start up to but not including end
while (curr != end)Reverse nodes until reaching end boundary
ListNode groupNext = kth.next;Save next group's start before reversal
tmp.next = groupNext;Reconnect reversed group to next part
#include <iostream>
using namespace std;

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

class Solution {
public:
    ListNode* reverseBetween(ListNode* start, ListNode* end) {
        ListNode* prev = nullptr;
        ListNode* curr = start;
        while (curr != end) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        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 != nullptr && count < k) {
                kth = kth->next;
                count++;
            }
            if (count < k) break;
            ListNode* groupNext = kth->next;

            ListNode* prev = reverseBetween(groupPrev->next, groupNext);

            ListNode* tmp = groupPrev->next;
            groupPrev->next = prev;
            tmp->next = groupNext;
            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 != nullptr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}
Line Notes
ListNode* reverseBetween(ListNode* start, ListNode* end)Helper reverses nodes from start up to but not including end
while (curr != end)Reverse nodes until end boundary
ListNode* groupNext = kth->next;Save next group's start before reversal
tmp->next = groupNext;Reconnect reversed group to next part
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function reverseBetween(start, end) {
    let prev = null;
    let curr = start;
    while (curr !== end) {
        let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

function reverseKGroup(head, k) {
    const dummy = new ListNode(0, 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 = reverseBetween(groupPrev.next, groupNext);

        const tmp = groupPrev.next;
        groupPrev.next = prev;
        tmp.next = groupNext;
        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;
const output = [];
while (curr !== null) {
    output.push(curr.val);
    curr = curr.next;
}
console.log(output.join(' '));
Line Notes
function reverseBetween(start, end)Helper reverses nodes from start up to but not including end
while (curr !== end)Reverse nodes until end boundary
const groupNext = kth.next;Save next group's start before reversal
tmp.next = groupNext;Reconnect reversed group to next part
⏱
Complexity
TimeO(n)
SpaceO(1)

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

💡 For n=20 and k=2, the algorithm does about 20 node visits and pointer changes with no extra memory.
Interview Verdict: Accepted and clean modular code

This approach is ideal for writing clean, maintainable code in interviews.

📊
All Approaches - One-Glance Tradeoffs
💡 The iterative approach with dummy node is the best choice in 95% of interviews due to its efficiency and clarity.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute Force (Recursive)O(n)O(n/k) recursion stackYes (deep recursion)YesMention only - never code
2. Iterative with Dummy NodeO(n)O(1)NoYesCode this approach
3. Iterative with Helper FunctionO(n)O(1)NoYesCode for clean modularity
💼
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 understanding. Next, present the optimal iterative solution, and finally discuss edge cases and testing.

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 dummy node as the optimal solution.Step 4: Discuss edge cases and how your code handles them.Step 5: Write clean code and test with sample inputs.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your ability to manipulate pointers correctly, handle edge cases, optimize for time and space, and write clean, bug-free code.

Common Follow-ups

  • What if k is larger than the list length? → Return the list as is.
  • Can you do this in constant extra space? → Yes, by reversing in place iteratively.
💡 These follow-ups check your understanding of boundary conditions and space optimization.
🔍
Pattern Recognition

When to Use

1) You need to reverse nodes in fixed-size groups; 2) The problem involves linked list pointer manipulation; 3) Partial groups remain unchanged; 4) Constraints require O(1) space.

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 or rotating list are related but different patterns.

Similar Problems

Reverse Linked List - simpler full reversalReverse Nodes in Even Length Groups - variation with group size changes

Practice

(1/5)
1. Consider the following code snippet implementing the optimal approach to copy a list with random pointers. Given the input list: 1 -> 2 -> 3, where node 1's random points to node 3, node 2's random points to node 1, and node 3's random is null, what is the value of copy_curr.random.val after the last iteration of the separation step (Step 3)?
easy
A. 1
B. 3
C. None (random pointer is null)
D. 2

Solution

  1. Step 1: Trace Step 1 (Interleaving nodes)

    Original list: 1->2->3. After interleaving: 1->1'->2->2'->3->3'.
  2. Step 2: Trace Step 2 (Assign random pointers)

    Node 1's random points to 3, so 1'.random = 3'. Node 2's random points to 1, so 2'.random = 1'. Node 3's random is null, so 3'.random = null.
  3. Step 3: Trace Step 3 (Separate lists)

    After separation, copy_curr starts at 1'. After last iteration, copy_curr is at 3'. Its random pointer is null, so copy_curr.random.val does not exist.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    copy_curr.random is null after last iteration [OK]
Hint: Random pointers point to copied nodes via original's next [OK]
Common Mistakes:
  • Confusing original and copied nodes during separation
  • Off-by-one error in advancing copy_curr
  • Assuming random pointers remain unchanged
2. Given the following code for odd-even linked list rearrangement, what is the output list after running the function on the input list [1, 2, 3, 4]?
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def oddEvenList(head):
    if not head or not head.next:
        return head
    odd = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    odd.next = even_head
    return head

# Input list: 1 -> 2 -> 3 -> 4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
new_head = oddEvenList(head)
curr = new_head
res = []
while curr:
    res.append(curr.val)
    curr = curr.next
print(res)
easy
A. [1, 2, 3, 4]
B. [1, 3, 2, 4]
C. [2, 4, 1, 3]
D. [1, 3, 4, 2]

Solution

  1. Step 1: Trace first iteration of while loop

    odd=1, even=2, even.next=3; odd.next=3, odd moves to 3; even.next=4, even moves to 4.
  2. Step 2: Loop ends as even.next is null; link odd.next to even_head (2)

    Final list order: 1 -> 3 -> 2 -> 4.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Output matches expected odd-even rearrangement for input [1,2,3,4] [OK]
Hint: Odd nodes first, then even nodes in original order [OK]
Common Mistakes:
  • Confusing node values with indices
  • Off-by-one errors in pointer updates
3. Given the following code snippet for splitting a linked list into k=3 parts, and the input list 1->2->3->4, what is the returned list of parts (values only)?
easy
A. [[1, 2], [3, 4], []]
B. [[1, 2], [3], [4]]
C. [[1, 2], [3], [4, None]]
D. [[1], [2], [3, 4]]

Solution

  1. Step 1: Calculate total nodes and part sizes

    Total nodes = 4, k = 3, so part_size = 1, remainder = 1. First remainder parts get one extra node.
  2. Step 2: Assign nodes to parts

    Part 0 size = 2 nodes (1,2), Part 1 size = 1 node (3), Part 2 size = 1 node (4). The returned parts are [[1,2],[3],[4]].
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Sum of parts equals original list length and sizes differ by at most one [OK]
Hint: Remainder nodes assigned to first parts -> first part larger [OK]
Common Mistakes:
  • Assigning remainder nodes to last parts
  • Off-by-one in part sizes
  • Returning fewer than k parts
4. Identify the bug in the following code snippet implementing the odd-even linked list rearrangement:
def oddEvenList(head):
    if not head or not head.next:
        return head
    odd = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    # Missing termination of even list
    odd.next = even_head
    return head
What is the consequence of the missing line and how to fix it?
medium
A. The function does not handle empty lists; fix by adding a check for head == None at the start
B. The odd pointer is not updated correctly inside the loop; fix by moving 'odd = odd.next' after even pointer updates
C. The even_head pointer is lost; fix by initializing even_head after the loop instead of before
D. The even list is not terminated with null, causing a cycle; fix by adding 'if even: even.next = None' before linking odd.next

Solution

  1. Step 1: Understand pointer termination

    Without setting even.next = None, the even list may still point to old nodes, causing cycles or infinite loops.
  2. Step 2: Fix by terminating even list

    Adding 'if even: even.next = None' before linking odd.next ensures even list ends properly.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Proper termination prevents cycles and infinite traversal [OK]
Hint: Always terminate the last node's next with None to avoid cycles [OK]
Common Mistakes:
  • Forgetting to terminate even list causing infinite loops
  • Misplacing pointer updates causing node skips
5. Suppose the multilevel doubly linked list can contain cycles via child pointers (i.e., a child pointer may point to an ancestor node). Which modification to the in-place iterative flattening algorithm correctly handles this scenario without infinite loops?
hard
A. Ignore cycles since the algorithm naturally terminates when curr is null.
B. Remove all child pointers before flattening to break cycles.
C. Use recursion with a depth limit to avoid infinite recursion.
D. Add a visited set to track nodes already processed and skip nodes if revisited.

Solution

  1. Step 1: Understand cycle problem

    Cycles via child pointers cause infinite loops if nodes are revisited during flattening.
  2. Step 2: Evaluate solutions

    Ignoring cycles (A) causes infinite loops. Removing child pointers (B) loses data. Recursion with depth limit (C) is unreliable. Tracking visited nodes (D) prevents revisiting and infinite loops.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Visited set prevents infinite loops in cyclic structures [OK]
Hint: Cycle detection requires tracking visited nodes explicitly [OK]
Common Mistakes:
  • Assuming no cycles exist in input
  • Relying on recursion depth limits
  • Ignoring child pointers that create cycles
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard