Remove Nth Node From End of List

🎯

Remove Nth Node From End of List

mediumTWO_POINTERAmazonMicrosoftFacebook

Imagine managing a playlist where you want to remove the song that is Nth from the end without counting the entire list every time.

💡 This problem is about linked list manipulation using two pointers. Beginners often struggle because they try to find the length first or use multiple passes, missing the elegant one-pass solution using a fixed gap between pointers.

📋

Problem Statement

Given the head of a singly linked list and an integer n, remove the nth node from the end of the list and return its head.

The number of nodes in the list is at least 1 and at most 10^51 ≤ n ≤ number of nodes in the list

💡

Example

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

Output[1,2,3,5]

The 2nd node from the end is '4'. Removing it results in the list [1,2,3,5].

• List has only one node and n=1 → result is an empty list
• n equals the length of the list → remove the head node
• n is 1 → remove the last node
• List with multiple nodes but all values are the same → ensure correct node is removed

⚠️

Common Mistakes

Not using a dummy node

Fails when removing the head node, causing null pointer errors or incorrect list

✅ Always use a dummy node pointing to head to simplify removal logic

Advancing fast pointer only n steps instead of n+1

Slow pointer ends up on the target node instead of the node before, causing incorrect removal

✅ Advance fast pointer n+1 steps to maintain correct gap

Not checking for null before accessing next

Runtime null pointer exceptions when list is short or at boundaries

✅ Use dummy node and carefully check pointers before dereferencing

Using recursion without considering stack overflow

Stack overflow for large lists causing program crash

✅ Prefer iterative two-pointer approach for large inputs

🧠

Brute Force (Two Pass Counting)

💡 This approach is the most straightforward and helps beginners understand the problem by breaking it down into counting and then removing, even though it's not optimal.

Intuition

First, count the total number of nodes. Then, find the (length - n)th node and remove the next node.

Algorithm

1. Traverse the list to count the total number of nodes.
2. Calculate the position to remove from the start: length - n.
3. Traverse again to the node just before the target node.
4. Adjust pointers to remove the target node and return the head.

💡 This approach is easy to visualize but requires two full traversals, which can be inefficient for large lists.

</>

Code

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

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    dummy = ListNode(0, head)
    current = dummy
    for _ in range(length - n):
        current = current.next
    current.next = current.next.next
    return dummy.next

# Driver code to test
if __name__ == '__main__':
    # Create linked list 1->2->3->4->5
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    new_head = removeNthFromEnd(head, 2)
    # Print list
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

length = 0Initialize length counter to zero before traversal to count nodes

while current:Traverse the entire list to count the total number of nodes

dummy = ListNode(0, head)Create a dummy node pointing to head to simplify edge cases like removing the head

for _ in range(length - n):Move current pointer to the node just before the one to remove

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

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
        ListNode dummy = new ListNode(0, head);
        current = dummy;
        for (int i = 0; i < length - n; i++) {
            current = current.next;
        }
        current.next = current.next.next;
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        Solution sol = new Solution();
        ListNode newHead = sol.removeNthFromEnd(head, 2);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

int length = 0;Initialize length counter before traversal to count nodes

while (current != null)Traverse the list to count the total number of nodes

ListNode dummy = new ListNode(0, head);Create dummy node to simplify edge cases like removing head

for (int i = 0; i < length - n; i++)Move current pointer to the node just before the one to remove

#include <iostream>
using namespace std;

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

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int length = 0;
        ListNode* current = head;
        while (current) {
            length++;
            current = current->next;
        }
        ListNode dummy(0);
        dummy.next = head;
        current = &dummy;
        for (int i = 0; i < length - n; i++) {
            current = current->next;
        }
        current->next = current->next->next;
        return dummy.next;
    }
};

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    Solution sol;
    ListNode* newHead = sol.removeNthFromEnd(head, 2);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

int length = 0;Initialize length counter before traversal to count nodes

while (current)Traverse the list to count the total number of nodes

ListNode dummy(0);Create dummy node to handle edge cases like removing head

for (int i = 0; i < length - n; i++)Advance current pointer to the node just before the one to remove

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

var removeNthFromEnd = function(head, n) {
    let length = 0;
    let current = head;
    while (current) {
        length++;
        current = current.next;
    }
    let dummy = new ListNode(0, head);
    current = dummy;
    for (let i = 0; i < length - n; i++) {
        current = current.next;
    }
    current.next = current.next.next;
    return dummy.next;
};

// Driver code
let head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
let newHead = removeNthFromEnd(head, 2);
let curr = newHead;
let output = [];
while (curr) {
    output.push(curr.val);
    curr = curr.next;
}
console.log(output.join(' '));

Line Notes

let length = 0;Initialize length counter before traversal to count nodes

while (current)Traverse the list to count the total number of nodes

let dummy = new ListNode(0, head);Create dummy node to simplify edge cases like removing head

for (let i = 0; i < length - n; i++)Move current pointer to the node just before the one to remove

⏱

Complexity

TimeO(2n) = O(n)

SpaceO(1)

Two passes over the list, each O(n), total O(n). Constant extra space for pointers.

💡 For n=10^5, this means about 200,000 steps, which is acceptable but can be improved.

Interview Verdict: Accepted but not optimal

This approach works but interviewers expect a one-pass solution for better efficiency.

🧠

One Pass Two Pointer (Fast and Slow)

💡 This approach introduces the two-pointer technique with a fixed gap, which is a common pattern in linked list problems and improves efficiency.

Intuition

Use two pointers separated by n nodes. Move both until the fast pointer reaches the end, then the slow pointer is just before the target node.

Algorithm

1. Create a dummy node pointing to head to handle edge cases.
2. Initialize two pointers, fast and slow, at the dummy node.
3. Move fast pointer n+1 steps ahead to maintain a gap, checking for null to avoid errors.
4. Move both pointers forward until fast reaches the end.
5. Slow pointer now points to the node before the target; remove target node.
6. Return dummy.next as the new head.

💡 The key is maintaining the gap so that slow lands exactly before the node to remove in one pass.

</>

Code

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

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n + 1):
        if fast is None:
            break
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

# Driver code
if __name__ == '__main__':
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    new_head = removeNthFromEnd(head, 2)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

dummy = ListNode(0, head)Create dummy node to simplify edge cases like removing the head

fast = slow = dummyInitialize both pointers at dummy to maintain a fixed gap

for _ in range(n + 1):Advance fast pointer n+1 steps to create the gap; check for None to avoid errors

while fast:Move both pointers forward until fast reaches the end, maintaining the gap

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

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy, slow = dummy;
        for (int i = 0; i <= n; i++) {
            if (fast == null) break;
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        Solution sol = new Solution();
        ListNode newHead = sol.removeNthFromEnd(head, 2);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

ListNode dummy = new ListNode(0, head);Create dummy node to handle edge cases like removing head

ListNode fast = dummy, slow = dummy;Initialize both pointers at dummy to maintain the gap

for (int i = 0; i <= n; i++)Advance fast pointer n+1 steps to create the gap; check for null to avoid errors

while (fast != null)Move both pointers forward until fast reaches the end, maintaining the gap

#include <iostream>
using namespace std;

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

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* fast = &dummy;
        ListNode* slow = &dummy;
        for (int i = 0; i <= n; i++) {
            if (fast == nullptr) break;
            fast = fast->next;
        }
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return dummy.next;
    }
};

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    Solution sol;
    ListNode* newHead = sol.removeNthFromEnd(head, 2);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

ListNode dummy(0);Create dummy node to simplify edge cases like removing head

ListNode* fast = &dummy;Initialize fast pointer at dummy to maintain gap

for (int i = 0; i <= n; i++)Advance fast pointer n+1 steps to create the gap; check for nullptr to avoid errors

while (fast)Move both pointers forward until fast reaches the end, maintaining the gap

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

var removeNthFromEnd = function(head, n) {
    let dummy = new ListNode(0, head);
    let fast = dummy, slow = dummy;
    for (let i = 0; i <= n; i++) {
        if (fast === null) break;
        fast = fast.next;
    }
    while (fast) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
};

// Driver code
let head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
let newHead = removeNthFromEnd(head, 2);
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, head);Create dummy node to handle edge cases like removing head

let fast = dummy, slow = dummy;Initialize both pointers at dummy to maintain the gap

for (let i = 0; i <= n; i++)Advance fast pointer n+1 steps to create the gap; check for null to avoid errors

while (fast)Move both pointers forward until fast reaches the end, maintaining the gap

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the list with two pointers, linear time and constant space.

💡 For n=10^5, this means about 100,000 steps, which is efficient for large inputs.

Interview Verdict: Accepted and optimal

This is the preferred approach in interviews due to its efficiency and elegance.

🧠

Recursive Approach (Backtracking)

💡 This approach uses recursion to reach the end of the list and counts back to find the node to remove, which helps understand recursion and backtracking in linked lists.

Intuition

Recursively traverse to the end, then count backwards. When count equals n, remove that node by adjusting pointers.

Algorithm

1. Define a recursive function that returns the index from the end.
2. Traverse to the end of the list recursively.
3. On returning, increment the index and check if it equals n.
4. If yes, remove the current node by adjusting pointers.
5. Return the head after recursion completes.

💡 This approach is elegant but can cause stack overflow for very large lists and is less efficient.

</>

Code

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

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        self.n = n
        def recurse(node):
            if not node:
                return 0
            idx = recurse(node.next) + 1
            if idx == self.n + 1:
                node.next = node.next.next
            return idx
        dummy = ListNode(0, head)
        recurse(dummy)
        return dummy.next

# Driver code
if __name__ == '__main__':
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    sol = Solution()
    new_head = sol.removeNthFromEnd(head, 2)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

def recurse(node):Recursive helper function to traverse to the end and count nodes backward

if not node:Base case: reached end of list, start counting back

idx = recurse(node.next) + 1Count index from end during backtracking phase

if idx == self.n + 1:When at node before target, remove the next node by adjusting pointers

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

public class Solution {
    private int n;
    private ListNode dummy;

    public ListNode removeNthFromEnd(ListNode head, int n) {
        this.n = n;
        dummy = new ListNode(0, head);
        recurse(dummy);
        return dummy.next;
    }

    private int recurse(ListNode node) {
        if (node == null) return 0;
        int idx = recurse(node.next) + 1;
        if (idx == n + 1) {
            node.next = node.next.next;
        }
        return idx;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        Solution sol = new Solution();
        ListNode newHead = sol.removeNthFromEnd(head, 2);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

private int recurse(ListNode node)Recursive helper function to count nodes from end

if (node == null) return 0;Base case for recursion: reached end of list

int idx = recurse(node.next) + 1;Count index from end during backtracking

if (idx == n + 1)Remove node after current when at correct position

#include <iostream>
using namespace std;

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

class Solution {
    int n;
    ListNode dummy = ListNode(0);
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        this->n = n;
        dummy.next = head;
        recurse(&dummy);
        return dummy.next;
    }

    int recurse(ListNode* node) {
        if (!node) return 0;
        int idx = recurse(node->next) + 1;
        if (idx == n + 1) {
            node->next = node->next->next;
        }
        return idx;
    }
};

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    Solution sol;
    ListNode* newHead = sol.removeNthFromEnd(head, 2);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

int recurse(ListNode* node)Recursive helper to count nodes from end

if (!node) return 0;Base case: end of list reached

int idx = recurse(node->next) + 1;Count index from end during backtracking

if (idx == n + 1)Remove node after current when at correct position

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

var removeNthFromEnd = function(head, n) {
    let dummy = new ListNode(0, head);
    function recurse(node) {
        if (!node) return 0;
        let idx = recurse(node.next) + 1;
        if (idx === n + 1) {
            node.next = node.next.next;
        }
        return idx;
    }
    recurse(dummy);
    return dummy.next;
};

// Driver code
let head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
let newHead = removeNthFromEnd(head, 2);
let curr = newHead;
let output = [];
while (curr) {
    output.push(curr.val);
    curr = curr.next;
}
console.log(output.join(' '));

Line Notes

function recurse(node)Recursive helper to count nodes from end

if (!node) return 0;Base case: reached end of list

let idx = recurse(node.next) + 1;Count index from end during backtracking

if (idx === n + 1)Remove node after current when at correct position

⏱

Complexity

TimeO(n)

SpaceO(n) due to recursion stack

Single traversal with recursion, but uses stack space proportional to list length.

💡 For large n, this can cause stack overflow, so iterative is preferred.

Interview Verdict: Accepted but less practical

Good for understanding recursion but not recommended for production or interviews due to stack depth.

📊

All Approaches - One-Glance Tradeoffs

💡 The one-pass two-pointer approach 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 (Two Pass Counting)	O(n)	O(1)	No	N/A	Mention only - never code
2. One Pass Two Pointer	O(n)	O(1)	No	N/A	Code this approach
3. Recursive Backtracking	O(n)	O(n) due to recursion stack	Yes	N/A	Mention as alternative, avoid coding

💼

Interview Strategy

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

How to Present

Step 1: Clarify input and output, including edge cases.Step 2: Present the brute force two-pass approach to show understanding.Step 3: Optimize to the one-pass two-pointer approach and explain the gap technique.Step 4: Optionally mention recursion to show breadth of knowledge.Step 5: Write clean code and test with edge cases.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your understanding of linked list traversal, pointer manipulation, and ability to optimize from naive to efficient solutions.

Common Follow-ups

• What if you want to remove the nth node from the start? → Just traverse n-1 steps and remove next.
• Can you do it without a dummy node? → Yes, but handling head removal becomes more complex.

💡 Follow-ups test your flexibility and understanding of edge cases and pointer safety.

🔍

Pattern Recognition

When to Use

1) Need to find nth element from end in a linked list, 2) Single pass preferred, 3) Problem mentions 'from end', 4) Linked list traversal with pointer manipulation

Signature Phrases

remove nth node from endlinked listsingle passtwo pointers

NOT This Pattern When

Problems that require sorting or random access arrays are different patterns.

Similar Problems

Remove Linked List Elements - similar pointer manipulationMiddle of the Linked List - uses slow and fast pointersLinked List Cycle - uses two pointers with different speeds

Practice

1. Given the following Python code implementing the optimal recursive addition of two linked lists representing numbers in forward order, what is the value of the carry returned by addListsHelper when adding lists representing 724 and 564?

easy

A. 1

B. 2

C. 0

D. 3

Solution

1. Step 1: Trace addition from least significant digit

   Adding 4 + 4 = 8, carry 0; next 2 + 6 = 8, carry 0; finally 7 + 5 = 12, carry 1.

2. Step 2: Propagate carry backward

   Carry 1 is returned from the most significant digit addition, indicating an overflow digit.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   724 + 564 = 1288, carry 1 at MSB addition [OK]

Hint: Carry is from MSB addition overflow [OK]

Common Mistakes:

• Ignoring carry from most significant digit
• Off-by-one error in recursion base case
• Misaligning lists before addition

2. Consider the following code that deletes a node from a singly linked list given only access to that node. What is the output after deleting the node with value 5?

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

def deleteNode(node):
    node.val = node.next.val
    node.next = node.next.next

n4 = ListNode(9)
n3 = ListNode(1, n4)
n2 = ListNode(5, n3)
n1 = ListNode(4, n2)

deleteNode(n2)

curr = n1
while curr:
    print(curr.val, end=' -> ' if curr.next else '\n')
    curr = curr.next

easy

A. 4 -> 9

B. 4 -> 1 -> 1 -> 9

C. 4 -> 1 -> 9

D. 4 -> 5 -> 1 -> 9

Solution

1. Step 1: Trace deleteNode on node with value 5

   Copy next node's value (1) into current node (5), so node.val becomes 1. Then update node.next to skip next node, pointing to node with value 9.

2. Step 2: Print the list after deletion

   List is now 4 -> 1 -> 9, as the original node with 5 is replaced by 1 and next points to 9.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Node 5 replaced by 1, next pointer updated correctly [OK]

Hint: Copy next node's value and skip next node [OK]

Common Mistakes:

• Forgetting to update next pointer, causing duplicates
• Printing original list without changes
• Confusing node values after deletion

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

4. Given the following recursive code to remove duplicates from a sorted linked list, what is the final list returned when the input list is [1, 2, 2, 3]?

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

def deleteDuplicates(head):
    if not head or not head.next:
        return head
    if head.val == head.next.val:
        val_to_remove = head.val
        while head and head.val == val_to_remove:
            head = head.next
        return deleteDuplicates(head)
    else:
        head.next = deleteDuplicates(head.next)
        return head

easy

A. [1, 2, 3]

B. [2, 3]

C. [1, 3]

D. [1]

Solution

1. Step 1: Trace initial call with head=1

   1 != 2, so recurse on deleteDuplicates(2 -> 2 -> 3).

2. Step 2: Trace call with head=2

   2 == 2, remove all nodes with val=2 by advancing head until head.val != 2, resulting in head=3. Recurse on deleteDuplicates(3).

3. Step 3: Trace call with head=3

   Only one node, return head as is.

4. Step 4: Reconstruct list

   From step 1, head=1, head.next = result from step 3 (3), so final list is [1, 3].

5. Final Answer:

   Option C -> Option C

6. Quick Check:

   Duplicates 2 removed completely, 1 and 3 remain [OK]

Hint: Duplicates removed recursively, only distinct nodes remain [OK]

Common Mistakes:

• Leaving one duplicate node
• Not skipping all duplicates in while loop
• Incorrectly linking nodes after recursion

5. Consider the following code snippet implementing the optimal rotation of a linked list. Given the list 1 -> 2 -> 3 -> None and k = 2, what is the value of new_head.val after rotation?

easy

A. 3

B. None (empty list)

C. 1

D. 2

Solution

1. Step 1: Calculate length and adjust k

   Length is 3, k=2%3=2, so rotation needed.

2. Step 2: Move fast pointer k steps ahead

   Fast moves from 1 -> 2 -> 3.

3. Step 3: Move slow and fast until fast reaches tail

   Slow moves from 1 -> 2, fast is at tail (3).

4. Step 4: Set new_head and break the list

   New head is slow.next = 3.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   New head value is 3 [OK]

Hint: Fast pointer moves k steps ahead [OK]

Common Mistakes:

• Off-by-one error in moving fast pointer
• Not adjusting k modulo length