Reverse Linked List II (Sublist)

🎯

Reverse Linked List II (Sublist)

mediumLINKED_LISTAmazonFacebookGoogle

Imagine editing a playlist by reversing a specific segment of songs without disturbing the rest - this problem is about reversing a sublist within a linked list in-place.

💡 This problem requires manipulating pointers within a linked list to reverse only a portion of it. Beginners often struggle because it involves careful pointer updates and edge cases like reversing at the head or tail of the list.

📋

Problem Statement

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

1 ≤ n ≤ 10^5 where n is the number of nodes in the linked list1 ≤ left ≤ right ≤ nThe linked list contains integer values

💡

Example

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

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

Only the sublist from position 2 to 4 is reversed, so nodes 2,3,4 become 4,3,2.

• left == right → list remains unchanged
• left == 1 and right == n → entire list reversed
• sublist at the end of the list → tail pointer updates
• single node list → no change

⚠️

Common Mistakes

Not using a dummy node

Fails when reversing sublist starting at head, causing null pointer errors

✅ Always use a dummy node pointing to head to simplify edge cases

Incorrect pointer updates during in-place reversal

Leads to cycles or broken lists, infinite loops or lost nodes

✅ Carefully update pointers in correct order, especially curr.next before moving nodes

Forgetting to reconnect the tail of reversed sublist

Sublist reversed but disconnected from rest of list, losing nodes

✅ After reversal, connect the tail of reversed sublist to afterRight node

Off-by-one errors in loops for left and right positions

Reverses wrong nodes or causes null pointer exceptions

✅ Carefully handle 1-based indexing and loop counts

Using recursion without considering stack overflow

Stack overflow on large lists, causing runtime errors

✅ Prefer iterative approach for large inputs or limit recursion depth

🧠

Brute Force (Extract, Reverse, Rebuild)

💡 This approach exists to build intuition by breaking the problem into simpler steps: extract the sublist, reverse it separately, then reconnect. It helps beginners understand the reversal concept before optimizing.

Intuition

Extract the sublist from left to right into a separate list, reverse it using a standard method, then reconnect it back to the original list.

Algorithm

1. Traverse the list to reach the node before position left (prevLeft).
2. Extract the sublist from left to right into a separate linked list.
3. Reverse the extracted sublist using a standard reversal method.
4. Reconnect the reversed sublist back between prevLeft and the node after right.

💡 This approach is easy to visualize but requires extra space and multiple passes, which is inefficient for large lists.

</>

Code

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

def reverseList(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

def reverseBetween(head, left, right):
    dummy = ListNode(0)
    dummy.next = head
    prevLeft = dummy
    for _ in range(left - 1):
        prevLeft = prevLeft.next
    sublist_head = prevLeft.next
    sublist_tail = sublist_head
    for _ in range(right - left):
        sublist_tail = sublist_tail.next
    afterRight = sublist_tail.next
    sublist_tail.next = None
    reversed_sublist = reverseList(sublist_head)
    prevLeft.next = reversed_sublist
    sublist_head.next = afterRight
    return dummy.next

# 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 = reverseBetween(nodes[0], 2, 4)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

dummy = ListNode(0)Create a dummy node to simplify edge cases like reversing from head

for _ in range(left - 1)Move prevLeft pointer to node before the sublist start

sublist_tail.next = NoneTemporarily break the list to isolate the sublist

reversed_sublist = reverseList(sublist_head)Reverse the isolated sublist separately

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

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prevLeft = dummy;
        for (int i = 0; i < left - 1; i++) {
            prevLeft = prevLeft.next;
        }
        ListNode sublistHead = prevLeft.next;
        ListNode sublistTail = sublistHead;
        for (int i = 0; i < right - left; i++) {
            sublistTail = sublistTail.next;
        }
        ListNode afterRight = sublistTail.next;
        sublistTail.next = null;
        ListNode reversedSublist = reverseList(sublistHead);
        prevLeft.next = reversedSublist;
        sublistHead.next = afterRight;
        return dummy.next;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        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];
        ListNode newHead = sol.reverseBetween(nodes[0], 2, 4);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

ListNode dummy = new ListNode(0);Dummy node simplifies handling reversal at head

for (int i = 0; i < left - 1; i++)Traverse to node before sublist start

sublistTail.next = null;Cut off sublist to reverse it independently

ListNode reversedSublist = reverseList(sublistHead);Reverse isolated sublist

#include <iostream>
using namespace std;

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

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* nxt = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nxt;
    }
    return prev;
}

ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* prevLeft = &dummy;
    for (int i = 0; i < left - 1; i++) {
        prevLeft = prevLeft->next;
    }
    ListNode* sublistHead = prevLeft->next;
    ListNode* sublistTail = sublistHead;
    for (int i = 0; i < right - left; i++) {
        sublistTail = sublistTail->next;
    }
    ListNode* afterRight = sublistTail->next;
    sublistTail->next = nullptr;
    ListNode* reversedSublist = reverseList(sublistHead);
    prevLeft->next = reversedSublist;
    sublistHead->next = afterRight;
    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];
    ListNode* newHead = reverseBetween(nodes[0], 2, 4);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

ListNode dummy(0);Dummy node helps handle edge cases cleanly

for (int i = 0; i < left - 1; i++)Move pointer to node before sublist

sublistTail->next = nullptr;Detach sublist for isolated reversal

ListNode* reversedSublist = reverseList(sublistHead);Reverse the isolated sublist

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function reverseList(head) {
    let prev = null;
    let curr = head;
    while (curr) {
        let nxt = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nxt;
    }
    return prev;
}

function reverseBetween(head, left, right) {
    let dummy = new ListNode(0);
    dummy.next = head;
    let prevLeft = dummy;
    for (let i = 0; i < left - 1; i++) {
        prevLeft = prevLeft.next;
    }
    let sublistHead = prevLeft.next;
    let sublistTail = sublistHead;
    for (let i = 0; i < right - left; i++) {
        sublistTail = sublistTail.next;
    }
    let afterRight = sublistTail.next;
    sublistTail.next = null;
    let reversedSublist = reverseList(sublistHead);
    prevLeft.next = reversedSublist;
    sublistHead.next = afterRight;
    return dummy.next;
}

// Test
const nodes = [1,2,3,4,5].map(v => new ListNode(v));
for (let i = 0; i < 4; i++) nodes[i].next = nodes[i+1];
const newHead = reverseBetween(nodes[0], 2, 4);
let curr = newHead;
let output = [];
while (curr) {
    output.push(curr.val);
    curr = curr.next;
}
console.log(output.join(' '));

Line Notes

let dummy = new ListNode(0);Dummy node simplifies edge cases like reversing from head

for (let i = 0; i < left - 1; i++)Traverse to node before sublist start

sublistTail.next = null;Cut off sublist to reverse it independently

let reversedSublist = reverseList(sublistHead);Reverse isolated sublist

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse the list multiple times: once to reach left, once to reach right, and once to reverse the sublist. The reversal itself is O(right-left+1). The extra space is due to creating a separate reversed sublist.

💡 For n=10^5, this means roughly 3 passes over the list, which is acceptable but not optimal.

Interview Verdict: Accepted but not optimal

This approach works but uses extra space and multiple passes, so it's good for understanding but not ideal for interviews.

🧠

In-Place Reversal Using Iterative Pointer Manipulation

💡 This approach improves on the brute force by reversing the sublist in-place during a single pass, avoiding extra space and multiple traversals.

Intuition

Use three pointers to reverse the sublist in-place by iteratively moving nodes from the sublist to the front of the reversed section.

Algorithm

1. Create a dummy node pointing to head to handle edge cases.
2. Move a pointer prev to the node before position left.
3. Set a pointer curr to prev.next (start of sublist).
4. Iteratively move the node after curr to after prev, effectively reversing the sublist in-place.

💡 This approach is tricky because it changes pointers inside the sublist while keeping track of connections outside it.

</>

Code

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

def reverseBetween(head, left, right):
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
    for _ in range(left - 1):
        prev = prev.next
    curr = prev.next
    for _ in range(right - left):
        temp = curr.next
        curr.next = temp.next
        temp.next = prev.next
        prev.next = temp
    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 = reverseBetween(nodes[0], 2, 4)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

dummy = ListNode(0)Dummy node simplifies handling reversal at head

for _ in range(left - 1)Move prev pointer to node before sublist

temp = curr.nextPick the node to be moved to front of reversed sublist

prev.next = tempInsert picked node immediately after prev

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

public class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }
        ListNode curr = prev.next;
        for (int i = 0; i < right - left; i++) {
            ListNode temp = curr.next;
            curr.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        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];
        ListNode newHead = sol.reverseBetween(nodes[0], 2, 4);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

ListNode dummy = new ListNode(0);Dummy node to handle edge cases cleanly

for (int i = 0; i < left - 1; i++)Traverse to node before sublist start

ListNode temp = curr.next;Node to be moved to front of reversed sublist

prev.next = temp;Insert node immediately after prev to reverse sublist

#include <iostream>
using namespace std;

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

ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* prev = &dummy;
    for (int i = 0; i < left - 1; i++) {
        prev = prev->next;
    }
    ListNode* curr = prev->next;
    for (int i = 0; i < right - left; i++) {
        ListNode* temp = curr->next;
        curr->next = temp->next;
        temp->next = prev->next;
        prev->next = temp;
    }
    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];
    ListNode* newHead = reverseBetween(nodes[0], 2, 4);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

ListNode dummy(0);Dummy node simplifies edge cases

for (int i = 0; i < left - 1; i++)Move prev pointer to node before sublist

ListNode* temp = curr->next;Node to be repositioned at front of reversed sublist

prev->next = temp;Insert node immediately after prev to reverse sublist

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function reverseBetween(head, left, right) {
    let dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    for (let i = 0; i < left - 1; i++) {
        prev = prev.next;
    }
    let curr = prev.next;
    for (let i = 0; i < right - left; i++) {
        let temp = curr.next;
        curr.next = temp.next;
        temp.next = prev.next;
        prev.next = temp;
    }
    return dummy.next;
}

// Test
const nodes = [1,2,3,4,5].map(v => new ListNode(v));
for (let i = 0; i < 4; i++) nodes[i].next = nodes[i+1];
const newHead = reverseBetween(nodes[0], 2, 4);
let curr = newHead;
let output = [];
while (curr) {
    output.push(curr.val);
    curr = curr.next;
}
console.log(output.join(' '));

Line Notes

let dummy = new ListNode(0);Dummy node to handle edge cases like reversal at head

for (let i = 0; i < left - 1; i++)Traverse to node before sublist start

let temp = curr.next;Node to be moved to front of reversed sublist

prev.next = temp;Insert node immediately after prev to reverse sublist

⏱

Complexity

TimeO(n)

SpaceO(1)

We traverse the list once to reach the sublist start and then reverse the sublist in-place with constant extra space.

💡 For n=10^5, this means a single pass with no extra memory, which is efficient and scalable.

Interview Verdict: Accepted and optimal

This is the preferred approach in interviews because it is efficient and uses constant space.

🧠

Recursive Approach to Reverse Sublist

💡 This approach uses recursion to reverse the sublist, which helps understand the problem from a different perspective and can be elegant but less intuitive for beginners.

Intuition

Recursively move to the left position, then reverse the next (right - left + 1) nodes, reconnecting as recursion unwinds.

Algorithm

1. Define a helper function to reverse the first n nodes of a list.
2. Recursively move head forward until left == 1.
3. Use the helper to reverse the first (right - left + 1) nodes.
4. Reconnect reversed sublist with the rest of the list.

💡 Recursion abstracts the pointer manipulation but requires careful base cases and understanding of recursion flow.

</>

Code

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

successor = None

def reverseN(head, n):
    global successor
    if n == 1:
        successor = head.next
        return head
    last = reverseN(head.next, n - 1)
    head.next.next = head
    head.next = successor
    return last

def reverseBetween(head, left, right):
    if left == 1:
        return reverseN(head, right)
    head.next = reverseBetween(head.next, left - 1, right - 1)
    return head

# 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 = reverseBetween(nodes[0], 2, 4)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

if n == 1:Base case: stop recursion after reversing n nodes

successor = head.nextStore the node after reversed sublist to reconnect later

head.next.next = headReverse pointer direction between two nodes

head.next = successorReconnect reversed sublist to the rest of the list

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

public class Solution {
    private ListNode successor = null;

    public ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = successor;
        return last;
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            return reverseN(head, right);
        }
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        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];
        ListNode newHead = sol.reverseBetween(nodes[0], 2, 4);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

if (n == 1)Base case to stop recursion after reversing n nodes

successor = head.next;Keep track of node after reversed sublist for reconnection

head.next.next = head;Reverse pointer direction between two nodes

head.next = successor;Reconnect reversed sublist to remainder of list

#include <iostream>
using namespace std;

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

ListNode* successor = nullptr;

ListNode* reverseN(ListNode* head, int n) {
    if (n == 1) {
        successor = head->next;
        return head;
    }
    ListNode* last = reverseN(head->next, n - 1);
    head->next->next = head;
    head->next = successor;
    return last;
}

ListNode* reverseBetween(ListNode* head, int left, int right) {
    if (left == 1) {
        return reverseN(head, right);
    }
    head->next = reverseBetween(head->next, left - 1, right - 1);
    return head;
}

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];
    ListNode* newHead = reverseBetween(nodes[0], 2, 4);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

if (n == 1)Base case to stop recursion after reversing n nodes

successor = head->next;Store node after reversed sublist for reconnection

head->next->next = head;Reverse pointer direction between two nodes

head->next = successor;Reconnect reversed sublist to remainder of list

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

let successor = null;

function reverseN(head, n) {
    if (n === 1) {
        successor = head.next;
        return head;
    }
    let last = reverseN(head.next, n - 1);
    head.next.next = head;
    head.next = successor;
    return last;
}

function reverseBetween(head, left, right) {
    if (left === 1) {
        return reverseN(head, right);
    }
    head.next = reverseBetween(head.next, left - 1, right - 1);
    return head;
}

// Test
const nodes = [1,2,3,4,5].map(v => new ListNode(v));
for (let i = 0; i < 4; i++) nodes[i].next = nodes[i+1];
const newHead = reverseBetween(nodes[0], 2, 4);
let curr = newHead;
let output = [];
while (curr) {
    output.push(curr.val);
    curr = curr.next;
}
console.log(output.join(' '));

Line Notes

if (n === 1)Base case to stop recursion after reversing n nodes

successor = head.next;Store node after reversed sublist for reconnection

head.next.next = head;Reverse pointer direction between two nodes

head.next = successor;Reconnect reversed sublist to remainder of list

⏱

Complexity

TimeO(n)

SpaceO(n)

Recursion depth can be up to n, so time is linear but space is linear due to call stack.

💡 For large n, recursion may cause stack overflow, so iterative is preferred.

Interview Verdict: Accepted but less practical

Elegant but recursion depth and complexity make it less ideal for interviews compared to iterative.

📊

All Approaches - One-Glance Tradeoffs

💡 The in-place iterative approach is the best choice for interviews due to its efficiency and constant space. Brute force is good for understanding, recursion for elegance but less practical.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Extract, Reverse, Rebuild)	O(n)	O(n)	No	Yes	Mention only - never code
2. In-Place Iterative Reversal	O(n)	O(1)	No	Yes	Code this approach
3. Recursive Reversal	O(n)	O(n)	Yes	Yes	Mention if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding, and finally present the optimal in-place solution.

How to Present

Step 1: Clarify the problem and constraints, including indexing and edge cases.Step 2: Describe the brute force approach by extracting and reversing the sublist separately.Step 3: Optimize to the in-place iterative reversal approach.Step 4: Optionally mention the recursive approach if time permits.Step 5: Write clean, tested code and discuss edge cases.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your understanding of linked list pointer manipulation, edge case handling, and ability to optimize from a naive to an in-place solution.

Common Follow-ups

• What if the list is doubly linked? → Reverse pointers in both directions similarly.
• Can you reverse every k nodes? → Use similar in-place reversal in groups.
• How to handle invalid left/right? → Validate inputs before processing.
• What if the list is circular? → Break the circle temporarily or adjust pointers carefully.

💡 These follow-ups test your ability to adapt the core reversal logic to variations and handle robustness.

🔍

Pattern Recognition

When to Use

1) You need to reverse a portion of a linked list, 2) The problem specifies left and right positions, 3) In-place reversal is required, 4) Edge cases involve head or tail sublists.

Signature Phrases

reverse the nodes from position left to rightin-place reversal of a sublist

NOT This Pattern When

Reversing entire list without sublist boundaries or problems involving list rotations

Similar Problems

Reverse Linked List I - full list reversal is a simpler versionReverse Nodes in k-Group - group-wise reversal using similar pointer techniques

Practice

1. You are given a singly linked list with unsorted integer values. You need to sort the list in ascending order with O(n log n) time complexity and O(1) auxiliary space. Which algorithmic approach best fits this requirement?

easy

A. Perform a bottom-up iterative merge sort directly on the linked list without extra arrays.

B. Use a recursive quicksort on the linked list by partitioning around a pivot node.

C. Extract all values into an array, sort the array using quicksort, then rebuild the linked list.

D. Apply a greedy insertion sort by inserting nodes into a new sorted list one by one.

Solution

1. Step 1: Understand time and space constraints

   The problem requires O(n log n) time and O(1) auxiliary space, which rules out array extraction and recursive approaches that use extra space.

2. Step 2: Identify algorithm matching constraints

   Bottom-up iterative merge sort on linked lists achieves O(n log n) time and O(1) space by merging sublists iteratively without recursion or extra arrays.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bottom-up merge sort is the standard in-place linked list sorting method [OK]

Hint: Bottom-up merge sort is in-place and O(n log n) [OK]

Common Mistakes:

• Thinking quicksort is efficient on linked lists due to lack of random access
• Assuming insertion sort is efficient for large lists
• Believing array extraction is O(1) space

2. What is the time and space complexity of the optimal in-place iterative merge algorithm for merging two sorted linked lists of lengths n and m?

medium

A. Time: O(max(n, m)), Space: O(1)

B. Time: O(n·m), Space: O(1)

C. Time: O(n + m), Space: O(n + m)

D. Time: O(n + m), Space: O(1)

Solution

1. Step 1: Analyze time complexity

   The algorithm traverses each node exactly once, either from l1 or l2, so total steps are proportional to n + m.

2. Step 2: Analyze space complexity

   It rearranges pointers in-place without allocating new nodes or recursion stack, so auxiliary space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space for in-place merge [OK]

Hint: In-place merge visits each node once, no extra space [OK]

Common Mistakes:

• Confusing time as O(n·m) due to nested loops
• Assuming recursion adds O(n + m) stack space
• Thinking space is O(n + m) due to new list creation

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

medium

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

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

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

D. Line: k = k % length

Solution

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

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

2. Step 2: Identify the bug

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

3. Step 3: Correct fix

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

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Correct break is slow.next = None [OK]

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

Common Mistakes:

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

4. Suppose you want to delete a node in a singly linked list given only access to that node, but now the node to delete might be the tail node. Which of the following statements is true about the optimal in-place deletion approach that copies the next node's data and deletes the next node?

hard

A. You must traverse from head to delete the tail node since no next node exists.

B. It works perfectly for tail nodes by copying data from a dummy next node.

C. You can delete the tail node by setting its value to None and next to None.

D. It cannot delete the tail node because there is no next node to copy from.

Solution

1. Step 1: Understand the limitation of the approach

   The method copies data from the next node and deletes the next node, so it requires a next node.

2. Step 2: Analyze tail node case

   The tail node has no next node, so this approach cannot be applied to delete the tail node.

3. Step 3: Consider alternatives

   Deleting the tail node requires access to the head to update the previous node's next pointer.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Tail node deletion requires head access, not possible with this method [OK]

Hint: Tail node has no next node to copy from [OK]

Common Mistakes:

• Assuming tail node can be deleted with same method
• Trying to create dummy next node to fix tail deletion
• Setting tail node value to None without pointer updates

5. Suppose the problem is modified so that the input list is no longer sorted. Which of the following approaches correctly removes all duplicates, leaving only distinct nodes, while maintaining O(n) time complexity?

hard

A. Use a hash map to count occurrences of each value, then reconstruct the list with only unique values.

B. Use the original recursive approach assuming sorted input; it still works correctly.

C. Sort the list first, then apply the original duplicate removal algorithm.

D. Use nested loops to compare each node with all others and remove duplicates in place.

Solution

1. Step 1: Understand problem change

   Input list is unsorted, so consecutive duplicates are not guaranteed.

2. Step 2: Evaluate approaches

   Original recursive approach relies on sorted order and fails on unsorted lists. Sorting first adds O(n log n) time. Nested loops are O(n²). Using a hash map to count occurrences and then reconstructing the list achieves O(n) time.

3. Step 3: Confirm time complexity

   Hash map counting and single pass reconstruction both run in O(n) time.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash map approach handles unsorted input efficiently [OK]

Hint: Unsorted input requires counting occurrences, not just skipping duplicates [OK]

Common Mistakes:

• Applying sorted-list algorithm directly
• Ignoring sorting cost
• Using nested loops for O(n) claim