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 singly linked list where each node contains an additional pointer that can point to any node in the list or null. The task is to create a deep copy of this list, preserving both the next and random pointer structure. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?

easy

A. Interleave copied nodes within the original list, assign random pointers using the interleaved structure, then separate the lists.

B. Use a hash map to store original-to-copy node mappings and create the copy in two passes.

C. Use a recursive function with memoization to copy nodes and their random pointers.

D. Traverse the list multiple times, copying nodes and random pointers separately without extra data structures.

Solution

1. Step 1: Understand the problem constraints

   The problem requires copying a complex linked list with random pointers efficiently.

2. Step 2: Identify the optimal approach

   Interleaving copied nodes within the original list allows assigning random pointers without extra space, then separating the lists restores the original and creates the copy.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Interleaving nodes achieves O(n) time and O(1) space [OK]

Hint: Interleaving nodes avoids extra space for mapping [OK]

Common Mistakes:

• Assuming recursion is always optimal
• Using extra hash maps increases space complexity
• Trying multiple traversals without mapping fails random pointer assignment

2. Given the following code snippet implementing the in-place iterative flattening of a multilevel doubly linked list, and the input list: 1 <-> 2 <-> 3, where node 2 has a child list 4 <-> 5, what is the value of curr.val after the first iteration of the outer while loop?

easy

A. 1

B. 4

C. 2

D. 3

Solution

1. Step 1: Initial state

   curr starts at node with val=1. First iteration: curr=1, no child, move to curr.next=2.

2. Step 2: First iteration with child

   curr=2 has child list starting at 4. The code finds tail=5, connects tail.next to curr.next (3), updates pointers, sets curr.next=4, child.prev=2, curr.child=None, then moves curr=curr.next=4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   After first iteration, curr moves to child node 4 [OK]

Hint: After splicing child, curr moves to child's head node [OK]

Common Mistakes:

• Assuming curr stays at original node after splicing
• Forgetting to move curr to next after flattening
• Confusing tail with child head

3. 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

4. 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)

5. Suppose the problem is modified so that the linked list nodes can be reused across parts (i.e., nodes can appear in multiple parts). Which of the following changes to the algorithm correctly handles this variant?

hard

A. No changes needed; the original algorithm already supports node reuse by splitting normally.

B. Modify the algorithm to skip cutting pointers and just record start nodes for each part, allowing overlap.

C. Use a hash map to track nodes already assigned and avoid duplicates during splitting.

D. Instead of cutting the list, create new nodes for each part to allow reuse without modifying the original list.

Solution

1. Step 1: Understand node reuse requirement

   Nodes can appear in multiple parts, so original list must remain intact.

2. Step 2: Evaluate algorithm changes

   Original algorithm cuts pointers, destroying original list structure. To allow reuse, new nodes must be created for each part.

3. Step 3: Discard other options

   Skipping cutting pointers causes overlapping parts but does not create separate nodes. Hash map tracking is unnecessary and inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Creating new nodes preserves original list and allows reuse [OK]

Hint: Node reuse requires copying nodes, not pointer cutting [OK]

Common Mistakes:

• Assuming original algorithm supports reuse
• Trying to reuse nodes without copying
• Overcomplicating with tracking structures