Reverse Linked List in Groups of K (Generalization)

🎯

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.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive)	O(n)	O(n/k) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Iterative with Dummy Node	O(n)	O(1)	No	Yes	Code this approach
3. Iterative with Helper Function	O(n)	O(1)	No	Yes	Code 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. You are given a doubly linked list where some nodes have a child pointer to another doubly linked list. The child list may also have one or more children of its own, and so on, creating a multilevel data structure. Which approach guarantees an optimal solution to flatten this multilevel doubly linked list into a single-level doubly linked list preserving the original order?

easy

A. Use a recursive depth-first traversal that returns the tail of each flattened child list and connects it back to the parent list.

B. Use a breadth-first traversal with a queue to process nodes level by level, appending child lists at the end of the current level.

C. Iteratively traverse the list, and whenever a node has a child, find the tail of the child list and splice it between the current node and its next node, updating all pointers in-place without extra space.

D. Apply a greedy approach that always flattens the child list with the largest number of nodes first to minimize pointer updates.

Solution

1. Step 1: Understand the problem structure

   The problem requires flattening a multilevel doubly linked list into a single-level list while preserving the order of nodes as they appear in depth-first traversal.

2. Step 2: Evaluate approaches

   Recursive DFS (A) works but uses extra stack space. The in-place iterative approach (B) efficiently flattens by splicing child lists without extra space. BFS (C) changes order and is not optimal. Greedy (D) does not guarantee correct order.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   In-place iterative flattening preserves order and uses O(1) extra space [OK]

Hint: In-place iterative splicing preserves order and uses no extra space [OK]

Common Mistakes:

• Confusing BFS with DFS order
• Assuming recursion is always optimal
• Thinking greedy approach reduces pointer updates

2. Given the following code for partitioning a linked list around value x = 3, and the input list: 1 -> 4 -> 2 -> 5, what is the final reordered list returned by the function?

easy

A. 1 -> 4 -> 2 -> 5

B. 1 -> 2 -> 4 -> 5

C. 2 -> 1 -> 4 -> 5

D. 4 -> 1 -> 2 -> 5

Solution

1. Step 1: Trace initial pointers with input 1 -> 4 -> 2 -> 5 and x=3

   Start with dummy -> 1 -> 4 -> 2 -> 5, less_tail and prev at dummy, current at 1.

2. Step 2: Process nodes

   Node 1 < 3, less_tail.next == current, move less_tail and prev forward. Node 4 >= 3, move prev and current forward. Node 2 < 3, less_tail.next != current, so remove 2 and insert after less_tail. Final list: 1 -> 2 -> 4 -> 5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Nodes less than 3 appear first in original order, then others [OK]

Hint: Track less_tail and prev carefully to avoid skipping nodes [OK]

Common Mistakes:

• Swapping values instead of nodes
• Incorrect pointer updates causing lost nodes
• Assuming order changes within partitions

3. Identify the bug in the following code snippet implementing the optimal approach to copy a list with random pointers:

medium

A. Line assigning curr.next.random = curr.random.next misses null check for curr.random

B. In Step 3, copy_curr is never advanced, causing incorrect separation

C. In Step 1, new_node is linked incorrectly to curr.next

D. The function returns copy_head before fully separating the lists

Solution

1. Step 1: Analyze Step 3 separation loop

   copy_curr is initialized but never advanced inside the loop, so copied list links are not updated correctly.

2. Step 2: Identify fix

   Adding copy_curr = copy_curr.next inside the loop after updating copy_curr.next fixes the bug.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without advancing copy_curr, copied list remains partially linked [OK]

Hint: Check if both original and copy pointers advance in separation loop [OK]

Common Mistakes:

• Forgetting to advance copy_curr in separation
• Assuming random pointer null checks are missing (they are present)
• Mislinking new_node in Step 1 (correct here)

4. The following code attempts to reorder a linked list using the recursive approach. Identify the line containing the subtle bug that can cause infinite loops or cycles when traversing the reordered list.

def reorderList(head):
    def helper(front, back):
        if not back:
            return True
        if not helper(front, back.next):
            return False
        if front[0] == back or front[0].next == back:
            # Missing termination here
            return False
        tmp = front[0].next
        front[0].next = back
        back.next = tmp
        front[0] = tmp
        return True
    helper([head], head)

medium

A. Line with 'if not back: return True' -- base case incorrect

B. Line with 'if front[0] == back or front[0].next == back:' -- missing back.next = None

C. Line with 'front[0].next = back' -- incorrect pointer assignment

D. Line with 'front[0] = tmp' -- front pointer update is wrong

Solution

1. Step 1: Identify termination condition

   The condition checking if front meets back must terminate the list by setting back.next = None.

2. Step 2: Locate missing termination

   Line with 'if front[0] == back or front[0].next == back:' lacks 'back.next = None', causing cycles.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing null termination leads to infinite traversal [OK]

Hint: Termination must set back.next = None to avoid cycles [OK]

Common Mistakes:

• Forgetting to null-terminate reordered list
• Misplacing pointer updates
• Incorrect base case handling

5. Suppose the linked list nodes can be reused multiple times (i.e., the list is circular or nodes can appear multiple times). Which modification to the odd-even rearrangement algorithm is necessary to handle this scenario correctly?

hard

A. Add a visited set to track nodes already processed to avoid infinite loops or duplicates

B. No modification needed; the original in-place algorithm works correctly even with reused nodes

C. Convert the list to an array first, then reorder and reconstruct the list to handle duplicates

D. Use recursion to process nodes and detect cycles automatically

Solution

1. Step 1: Identify problem with reused nodes

   If nodes are reused or list is circular, naive pointer traversal causes infinite loops or duplicates.

2. Step 2: Use a visited set

   Tracking visited nodes prevents revisiting and infinite loops, ensuring correct rearrangement.

3. Step 3: Why other options fail

   No modification ignores cycles; array conversion adds overhead; recursion risks stack overflow without cycle detection.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Visited set is standard for cycle detection in linked lists [OK]

Hint: Detect cycles with visited set to avoid infinite loops [OK]

Common Mistakes:

• Assuming original algorithm handles cycles or reused nodes
• Using recursion without cycle detection