Rotate List

🎯

Rotate List

mediumLINKED_LISTAmazonGoogle

Imagine a conveyor belt of packages where the last few packages need to be moved to the front without rearranging the entire belt manually.

💡 This problem involves manipulating pointers in a linked list to rotate it. Beginners often struggle because it requires careful handling of list ends and understanding how to reconnect nodes without losing parts of the list.

📋

Problem Statement

Given the head of a linked list and an integer k, rotate the list to the right by k places. Return the rotated list's head.

The number of nodes in the list is in the range [1, 10^5].0 ≤ k ≤ 10^9

💡

Example

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

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

Rotating the list by 2 moves the last two nodes to the front.

Input"head = [0,1,2], k = 4"

Output[2,0,1]

Rotating by 4 is equivalent to rotating by 1 (4 mod 3), so the last node moves to front.

• Single node list → output same list
• k is zero → output same list
• k is multiple of list length → output same list
• List with two nodes and k = 1 → nodes swap places

⚠️

Common Mistakes

Not handling k greater than list length

Incorrect rotation or runtime errors

✅ Use k = k % length to reduce rotations

Breaking the list incorrectly after rotation

List becomes cyclic or truncated

✅ Ensure new tail's next is set to null

Not handling single node or empty list

Null pointer exceptions or wrong output

✅ Check for head == null or head.next == null early

Off-by-one errors in calculating new tail position

Rotation is off by one node

✅ Carefully compute steps to new tail as length - k - 1

Using slow and fast pointers incorrectly

Pointers don't find correct new tail, wrong rotation

✅ Advance fast pointer k steps before moving both

🧠

Brute Force (Repeated Single Rotations)

💡 This approach exists to build intuition by simulating the rotation step-by-step, even though it's inefficient. It helps beginners understand what rotation means in a linked list.

Intuition

Rotate the list by moving the last node to the front, one step at a time, repeating k times.

Algorithm

1. For each rotation from 1 to k:
2. Traverse to the second last node.
3. Detach the last node and move it to the front.
4. Update the head pointer to the new front node.

💡 The nested traversal makes this approach slow and hard to optimize, but it clearly shows how rotation affects the list.

</>

Code

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

def rotateRight(head, k):
    if not head or not head.next or k == 0:
        return head
    length = 1
    tail = head
    while tail.next:
        tail = tail.next
        length += 1
    k = k % length
    if k == 0:
        return head
    for _ in range(k):
        prev = None
        curr = head
        while curr.next:
            prev = curr
            curr = curr.next
        prev.next = None
        curr.next = head
        head = curr
    return head

# Driver code to test
if __name__ == '__main__':
    # Create 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]
    rotated = rotateRight(nodes[0], 2)
    curr = rotated
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

if not head or not head.next or k == 0:Handle trivial cases early to avoid unnecessary work

while tail.next:Find the length and tail of the list to know rotation bounds

k = k % lengthReduce k to avoid full rotations that return the list unchanged

for _ in range(k):Perform k single rotations by moving last node to front

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

public class Solution {
    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;
        int length = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            length++;
        }
        k = k % length;
        if (k == 0) return head;
        for (int i = 0; i < k; i++) {
            ListNode prev = null;
            ListNode curr = head;
            while (curr.next != null) {
                prev = curr;
                curr = curr.next;
            }
            prev.next = null;
            curr.next = head;
            head = curr;
        }
        return head;
    }

    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];
        ListNode rotated = rotateRight(nodes[0], 2);
        ListNode curr = rotated;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

if (head == null || head.next == null || k == 0) return head;Quickly return for trivial or no-rotation cases

while (tail.next != null)Calculate length and find tail node for rotation logic

k = k % length;Optimize k to avoid redundant full rotations

for (int i = 0; i < k; i++)Rotate one step at a time, k times

#include <iostream>
using namespace std;

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

ListNode* rotateRight(ListNode* head, int k) {
    if (!head || !head->next || k == 0) return head;
    int length = 1;
    ListNode* tail = head;
    while (tail->next) {
        tail = tail->next;
        length++;
    }
    k = k % length;
    if (k == 0) return head;
    for (int i = 0; i < k; i++) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr->next) {
            prev = curr;
            curr = curr->next;
        }
        prev->next = nullptr;
        curr->next = head;
        head = curr;
    }
    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* rotated = rotateRight(nodes[0], 2);
    ListNode* curr = rotated;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

if (!head || !head->next || k == 0) return head;Handle base cases to avoid unnecessary processing

while (tail->next)Traverse to find list length and tail node

k = k % length;Reduce k to effective rotations only

for (int i = 0; i < k; i++)Perform rotation one node at a time

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

function rotateRight(head, k) {
    if (!head || !head.next || k === 0) return head;
    let length = 1;
    let tail = head;
    while (tail.next) {
        tail = tail.next;
        length++;
    }
    k = k % length;
    if (k === 0) return head;
    for (let i = 0; i < k; i++) {
        let prev = null;
        let curr = head;
        while (curr.next) {
            prev = curr;
            curr = curr.next;
        }
        prev.next = null;
        curr.next = head;
        head = curr;
    }
    return head;
}

// Test 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 rotated = rotateRight(nodes[0], 2);
let curr = rotated;
let output = [];
while (curr) {
    output.push(curr.val);
    curr = curr.next;
}
console.log(output.join(' '));

Line Notes

if (!head || !head.next || k === 0) return head;Return early for trivial or no-op cases

while (tail.next)Find the length and tail node for rotation logic

k = k % length;Optimize k to avoid unnecessary full rotations

for (let i = 0; i < k; i++)Rotate the list one step at a time, k times

⏱

Complexity

TimeO(n*k)

SpaceO(1)

Each rotation requires traversing the list to find the last node, which is O(n). Doing this k times results in O(n*k).

💡 For n=5 and k=2, this means about 10 operations, but for large k like 10^5, this becomes very slow.

Interview Verdict: TLE for large k, but useful for understanding

This approach is too slow for large inputs but helps grasp the rotation concept before optimizing.

🧠

Better Approach (Calculate Length and Connect Tail to Head)

💡 This approach improves efficiency by avoiding repeated traversals, using the list length and connecting tail to head to form a ring, then breaking at the right point.

Intuition

Make the list circular by connecting tail to head, then find the new tail after rotation and break the ring there.

Algorithm

1. Find the length of the list and the tail node.
2. Connect the tail to the head to form a circular list.
3. Calculate the new tail position as length - (k % length) - 1.
4. Traverse to the new tail and break the ring by setting new tail's next to null.
5. Return the new head which is new tail's next.

💡 This approach cleverly uses the circular list concept to rotate in O(n) time without repeated traversals.

</>

Code

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

def rotateRight(head, k):
    if not head or not head.next or k == 0:
        return head
    length = 1
    tail = head
    while tail.next:
        tail = tail.next
        length += 1
    k = k % length
    if k == 0:
        return head
    tail.next = head  # connect tail to head to make it circular
    steps_to_new_tail = length - k - 1
    new_tail = head
    for _ in range(steps_to_new_tail):
        new_tail = new_tail.next
    new_head = new_tail.next
    new_tail.next = None  # break the ring
    return new_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]
    rotated = rotateRight(nodes[0], 2)
    curr = rotated
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

while tail.next:Find the length and tail node in one pass

tail.next = headMake the list circular to simplify rotation

steps_to_new_tail = length - k - 1Calculate how many steps to reach new tail after rotation

new_tail.next = NoneBreak the circular link to finalize rotated list

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

public class Solution {
    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;
        int length = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            length++;
        }
        k = k % length;
        if (k == 0) return head;
        tail.next = head; // connect tail to head
        int stepsToNewTail = length - k - 1;
        ListNode newTail = head;
        for (int i = 0; i < stepsToNewTail; i++) {
            newTail = newTail.next;
        }
        ListNode newHead = newTail.next;
        newTail.next = null; // break the ring
        return newHead;
    }

    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];
        ListNode rotated = rotateRight(nodes[0], 2);
        ListNode curr = rotated;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

while (tail.next != null)Traverse once to find length and tail

tail.next = head;Create circular linked list to simplify rotation

int stepsToNewTail = length - k - 1;Find new tail position after rotation

newTail.next = null;Break the circular link to finalize rotated list

#include <iostream>
using namespace std;

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

ListNode* rotateRight(ListNode* head, int k) {
    if (!head || !head->next || k == 0) return head;
    int length = 1;
    ListNode* tail = head;
    while (tail->next) {
        tail = tail->next;
        length++;
    }
    k = k % length;
    if (k == 0) return head;
    tail->next = head; // make circular
    int stepsToNewTail = length - k - 1;
    ListNode* newTail = head;
    for (int i = 0; i < stepsToNewTail; i++) {
        newTail = newTail->next;
    }
    ListNode* newHead = newTail->next;
    newTail->next = nullptr; // break the ring
    return newHead;
}

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

Line Notes

while (tail->next)Find length and tail in one traversal

tail->next = head;Connect tail to head to form a circular list

int stepsToNewTail = length - k - 1;Calculate steps to new tail after rotation

newTail->next = nullptr;Break the circular link to finalize rotated list

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

function rotateRight(head, k) {
    if (!head || !head.next || k === 0) return head;
    let length = 1;
    let tail = head;
    while (tail.next) {
        tail = tail.next;
        length++;
    }
    k = k % length;
    if (k === 0) return head;
    tail.next = head; // make circular
    let stepsToNewTail = length - k - 1;
    let newTail = head;
    for (let i = 0; i < stepsToNewTail; i++) {
        newTail = newTail.next;
    }
    let newHead = newTail.next;
    newTail.next = null; // break the ring
    return newHead;
}

// Test 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 rotated = rotateRight(nodes[0], 2);
let curr = rotated;
let output = [];
while (curr) {
    output.push(curr.val);
    curr = curr.next;
}
console.log(output.join(' '));

Line Notes

while (tail.next)Find length and tail node in one pass

tail.next = head;Create circular linked list to simplify rotation

let stepsToNewTail = length - k - 1;Calculate new tail position after rotation

newTail.next = null;Break the circular link to finalize rotated list

⏱

Complexity

TimeO(n)

SpaceO(1)

We traverse the list a constant number of times (to find length, then to new tail), so time is linear in n.

💡 For n=10^5, this means about 200,000 operations, which is efficient for interviews.

Interview Verdict: Accepted and efficient

This is the standard optimal approach to code in interviews for this problem.

🧠

Optimal Approach (Two Pointer Technique to Find New Tail)

💡 This approach uses two pointers spaced k apart to find the new tail in one pass after making the list circular, combining clarity and efficiency.

Intuition

After connecting tail to head, use two pointers where one advances k steps ahead, then move both until the front pointer reaches the tail, so the second pointer points to new tail.

Algorithm

1. Find the length and tail of the list.
2. Connect tail to head to form a circular list.
3. Move a fast pointer k steps ahead.
4. Move both slow and fast pointers until fast reaches tail.
5. Slow pointer now points to new tail; break the ring and return new head.

💡 This method avoids explicit arithmetic for new tail position and uses pointer spacing to find it.

</>

Code

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

def rotateRight(head, k):
    if not head or not head.next or k == 0:
        return head
    length = 1
    tail = head
    while tail.next:
        tail = tail.next
        length += 1
    k = k % length
    if k == 0:
        return head
    tail.next = head  # make circular
    fast = head
    for _ in range(k):
        fast = fast.next
    slow = head
    while fast != tail:
        slow = slow.next
        fast = fast.next
    new_head = slow.next
    slow.next = None
    return new_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]
    rotated = rotateRight(nodes[0], 2)
    curr = rotated
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

while tail.next:Find length and tail node in one pass

tail.next = headMake the list circular to simplify rotation

for _ in range(k):Advance fast pointer k steps ahead

while fast != tail:Move both pointers until fast reaches tail to find new tail

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

public class Solution {
    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;
        int length = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            length++;
        }
        k = k % length;
        if (k == 0) return head;
        tail.next = head; // make circular
        ListNode fast = head;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        ListNode slow = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
        }
        ListNode newHead = slow.next;
        slow.next = null;
        return newHead;
    }

    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];
        ListNode rotated = rotateRight(nodes[0], 2);
        ListNode curr = rotated;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

while (tail.next != null)Find length and tail node in one pass

tail.next = head;Make the list circular to simplify rotation

for (int i = 0; i < k; i++)Move fast pointer k steps ahead

while (fast != tail)Move both pointers until fast reaches tail to find new tail

#include <iostream>
using namespace std;

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

ListNode* rotateRight(ListNode* head, int k) {
    if (!head || !head->next || k == 0) return head;
    int length = 1;
    ListNode* tail = head;
    while (tail->next) {
        tail = tail->next;
        length++;
    }
    k = k % length;
    if (k == 0) return head;
    tail->next = head; // make circular
    ListNode* fast = head;
    for (int i = 0; i < k; i++) {
        fast = fast->next;
    }
    ListNode* slow = head;
    while (fast != tail) {
        slow = slow->next;
        fast = fast->next;
    }
    ListNode* newHead = slow->next;
    slow->next = nullptr;
    return newHead;
}

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

Line Notes

while (tail->next)Find length and tail node in one pass

tail->next = head;Make the list circular to simplify rotation

for (int i = 0; i < k; i++)Advance fast pointer k steps ahead

while (fast != tail)Move both pointers until fast reaches tail to find new tail

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

function rotateRight(head, k) {
    if (!head || !head.next || k === 0) return head;
    let length = 1;
    let tail = head;
    while (tail.next) {
        tail = tail.next;
        length++;
    }
    k = k % length;
    if (k === 0) return head;
    tail.next = head; // make circular
    let fast = head;
    for (let i = 0; i < k; i++) {
        fast = fast.next;
    }
    let slow = head;
    while (fast !== tail) {
        slow = slow.next;
        fast = fast.next;
    }
    let newHead = slow.next;
    slow.next = null;
    return newHead;
}

// Test 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 rotated = rotateRight(nodes[0], 2);
let curr = rotated;
let output = [];
while (curr) {
    output.push(curr.val);
    curr = curr.next;
}
console.log(output.join(' '));

Line Notes

while (tail.next)Find length and tail node in one pass

tail.next = head;Make the list circular to simplify rotation

for (let i = 0; i < k; i++)Advance fast pointer k steps ahead

while (fast !== tail)Move both pointers until fast reaches tail to find new tail

⏱

Complexity

TimeO(n)

SpaceO(1)

The list is traversed a constant number of times, so time complexity is linear.

💡 This approach is efficient and suitable for large inputs, making it ideal for interviews.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews for clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal two-pointer approach is recommended for interviews due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*k)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Circular List + Arithmetic	O(n)	O(1)	No	N/A	Good to code if comfortable with pointer arithmetic
3. Circular List + Two Pointers	O(n)	O(1)	No	N/A	Best approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of rotation.Discuss inefficiencies and propose the circular list optimization.Implement the optimal two-pointer approach.Test your code with edge cases and explain your reasoning.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your understanding of linked list pointer manipulation, edge case handling, and ability to optimize from brute force to linear time.

Common Follow-ups

• What if k is very large? → Use modulo with list length to optimize.
• Can you do this in one pass? → Use two pointers spaced k apart after making list circular.

💡 These follow-ups test your ability to handle large inputs and optimize pointer usage.

🔍

Pattern Recognition

When to Use

1) Problem involves rotating or shifting linked list nodes; 2) Rotation count k may be large; 3) Need in-place pointer manipulation; 4) Circular linked list or two-pointer technique is applicable.

Signature Phrases

rotate the list to the right by k placesmove last k nodes to front

NOT This Pattern When

Problems that require reordering nodes by value or sorting are different patterns.

Similar Problems

Reverse Linked List - also involves pointer manipulationRotate Array - similar rotation logic but on arraysLinked List Cycle - uses circular linked list concept

Practice

1. Consider the following Python code for merging two sorted linked lists in-place:

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

def mergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val > l2.val:
        l1, l2 = l2, l1
    head = l1
    while l1 and l2:
        prev = None
        while l1 and l1.val <= l2.val:
            prev = l1
            l1 = l1.next
        prev.next = l2
        l1, l2 = l2, l1
    return head

# Input lists:
# l1: 1 -> 3 -> 5
# l2: 2 -> 4

merged_head = mergeTwoLists(l1, l2)

What is the value of the node pointed to by prev after the first inner while loop iteration inside the outer while loop?

easy

A. Node with value 3

B. Node with value 5

C. Node with value 1

D. Node with value 2

Solution

1. Step 1: Trace the inner while loop with initial lists

   Initially, l1 points to 1, l2 points to 2. The inner loop advances l1 while l1.val <= l2.val: - l1=1 (<=2), prev=1, l1 moves to 3 - l1=3 (>2), loop stops

2. Step 2: Identify prev after loop

   Prev points to node with value 1 after the inner loop ends, which is the last node with value less than or equal to l2.val.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Prev points to last l1 node ≤ current l2 node [OK]

Hint: Prev points to last l1 node ≤ current l2 node [OK]

Common Mistakes:

• Assuming prev points to node with value 3 after first inner loop
• Confusing l1 and l2 pointers after swap
• Forgetting that prev updates inside inner loop

2. You are given a singly linked list and need to determine if it reads the same forwards and backwards without using extra space proportional to the list size. Which approach best guarantees an optimal solution in terms of time and space complexity?

easy

A. Convert the linked list to an array and check if the array is a palindrome.

B. Use a dynamic programming approach to store palindrome states for sublists.

C. Use a recursive two-pointer technique that compares nodes from front and back simultaneously.

D. Use a greedy approach by comparing nodes pairwise from start and end without recursion or extra space.

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking palindrome property in a linked list without using extra space proportional to the list size, ruling out array conversion.

2. Step 2: Analyze space and time complexity of options

   Convert the linked list to an array and check if the array is a palindrome. uses O(n) extra space for array; Use a dynamic programming approach to store palindrome states for sublists. uses O(n^2) time and space; Use a recursive two-pointer technique that compares nodes from front and back simultaneously. uses O(n) time but O(n) space due to recursion stack; Use a greedy approach by comparing nodes pairwise from start and end without recursion or extra space. uses O(n) time and O(1) space by reversing the second half and comparing.

3. Step 3: Identify optimal approach

   Use a greedy approach by comparing nodes pairwise from start and end without recursion or extra space. is optimal with O(n) time and O(1) space, meeting constraints without recursion overhead.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Greedy pairwise comparison with in-place reversal is optimal [OK]

Hint: In-place reversal of second half achieves O(1) space palindrome check [OK]

Common Mistakes:

• Assuming recursion uses no extra space
• Confusing DP with palindrome linked list
• Thinking array conversion is space optimal

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

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

What is the consequence of this bug?

medium

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

B. The node is correctly deleted with no issues.

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

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

Solution

1. Step 1: Analyze the code's effect

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

2. Step 2: Understand the consequence

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

3. Final Answer:

   Option A -> Option A

4. Quick Check:

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

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

Common Mistakes:

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

4. What is the time complexity of the optimal min-heap based algorithm for merging k sorted linked lists with a total of N nodes?

medium

A. O(N k) because each node is compared with nodes from all k lists.

B. O(N log N) because all nodes are pushed and popped from the heap.

C. O(kN) because each list is merged sequentially with all others.

D. O(N log k) because each of the N nodes is pushed and popped from a heap of size at most k.

Solution

1. Step 1: Identify heap operations per node

   Each node is pushed and popped exactly once from a heap of size ≤ k.

2. Step 2: Calculate complexity

   Heap push/pop cost is O(log k), total O(N log k) for N nodes.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Heap size depends on k, not N, so O(N log k) [OK]

Hint: Heap size is k, not N, so complexity is O(N log k) [OK]

Common Mistakes:

• Confusing N and k in log factor
• Assuming heap size grows with N
• Thinking sequential merges are optimal

5. Suppose you want to reverse a singly linked list that may contain cycles (i.e., some node's next pointer points to a previous node). Which modification to the standard tail-recursive reversal algorithm correctly handles this scenario without infinite recursion?

hard

A. Add a visited set to track nodes already reversed and stop recursion if a node repeats.

B. Use the standard tail-recursive reversal without changes; cycles will be reversed naturally.

C. Convert the list to an array first, then reverse the array and rebuild the list to avoid cycles.

D. Limit recursion depth to a fixed number to prevent infinite loops in cycles.

Solution

1. Step 1: Understand cycle problem

   Standard reversal assumes acyclic list; cycles cause infinite recursion or loops.

2. Step 2: Modify algorithm

   Tracking visited nodes prevents revisiting and infinite recursion by stopping when a node repeats.

3. Step 3: Evaluate other options

   Standard recursion (B) fails on cycles. Converting to array (C) is inefficient and not in-place. Limiting recursion depth (A) is arbitrary and unsafe.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Visited set detects cycles and prevents infinite recursion [OK]

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

Common Mistakes:

• Assuming input list is always acyclic
• Ignoring cycle detection in recursive reversal