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. Consider the following buggy code for finding the middle node of a linked list. Which line contains the subtle bug that can cause a runtime error?

medium

A. Line 4: while fast.next and fast.next.next:

B. Line 3: fast = head

C. Line 2: slow = head

D. Line 6: return slow

Solution

1. Step 1: Analyze loop condition

   The condition checks fast.next and fast.next.next but does not check if fast itself is null, which can cause AttributeError if fast is null.

2. Step 2: Identify fix

   Change condition to while fast and fast.next to safely access fast.next.next.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing fast null check causes runtime error on short lists [OK]

Hint: Always check fast pointer is not null before accessing next [OK]

Common Mistakes:

• Assuming fast.next is safe without checking fast
• Returning first middle node incorrectly
• Modifying list nodes accidentally

2. What is the time complexity of the optimal one-pass splitting algorithm for splitting a linked list of length n into k parts, and why?

medium

A. O(n + k) because we first count nodes in O(n) and then split in O(k) steps.

B. O(n * k) because for each of the k parts, we traverse nodes up to part size.

C. O(n) because we only traverse the list once without extra passes.

D. O(k) because we only create k parts and do constant work per part.

Solution

1. Step 1: Analyze counting nodes

   Counting total nodes requires traversing the entire list once -> O(n).

2. Step 2: Analyze splitting parts

   Splitting involves iterating over k parts and moving pointers, total steps sum to n nodes plus k iterations -> O(n + k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counting + splitting both contribute; total is O(n + k) [OK]

Hint: Counting nodes plus splitting parts sums to O(n + k) [OK]

Common Mistakes:

• Assuming O(n*k) due to nested loops
• Ignoring counting step
• Confusing k with n

3. Suppose the problem is modified so that the array elements can be zero, representing no movement, and cycles of length 1 (self-loop) are now considered valid. Which modification to the original fast and slow pointer algorithm correctly handles this variant?

hard

A. Remove the check that breaks when slow == next_index(slow), allowing single-element loops to return True.

B. Add a condition to skip zeros in the outer loop and treat zero jumps as invalid for cycles.

C. Modify the direction check to allow zero as both positive and negative direction to include zero jumps.

D. Use a visited set to track indices and return True if any index is revisited, ignoring direction.

Solution

1. Step 1: Understand new problem constraints

   Zero jumps are allowed and single-element loops are valid cycles.

2. Step 2: Identify necessary algorithm change

   The original code breaks when slow == next_index(slow) to exclude single-element loops; removing this check allows detecting single-element cycles.

3. Step 3: Confirm direction and zero handling

   Zeros represent no movement; allowing them means direction check must still be consistent, but zero jumps can form valid cycles.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing single-element loop break correctly detects new valid cycles [OK]

Hint: Allow single-element loops by removing cycle length >1 check [OK]

Common Mistakes:

• Skipping zeros entirely
• Treating zero as both directions
• Ignoring direction consistency

4. Suppose you want to find the middle node of a linked list, but the list is circular (the last node points back to the head). Which modification to the two-pointer approach correctly finds the middle node without infinite looping?

hard

A. Use the same two-pointer approach but add a visited set to detect cycles and stop when fast pointer revisits a node.

B. Use recursion to count nodes until the head is reached again, then find middle by index.

C. Convert the circular list to a linear list by breaking the cycle first, then apply the standard two-pointer approach.

D. Modify the loop to stop when fast or fast.next equals the head node, then return slow pointer.

Solution

1. Step 1: Understand circular list behavior

   In a circular list, fast pointer will loop infinitely unless we detect when it cycles back to head.

2. Step 2: Modify loop condition

   Stop when fast or fast.next equals head to avoid infinite loop; slow pointer will be at middle.

3. Step 3: Compare alternatives

   Visited set adds extra space; breaking cycle modifies input; recursion risks stack overflow.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Stopping at head detects cycle end without extra space [OK]

Hint: Detect cycle by checking if fast pointer returns to head [OK]

Common Mistakes:

• Using visited set wastes space
• Breaking cycle modifies input
• Recursion risks stack overflow

5. If the linked list allows cycles (i.e., it may not terminate), which modification is necessary to safely find the nth node from the end?

hard

A. Use the two-pointer approach without changes; it will still work.

B. Use a stack to store nodes indefinitely until nth node is found.

C. First detect cycle using Floyd's cycle detection, then handle accordingly before finding nth node.

D. Increase n to a very large number to ensure traversal covers the cycle.

Solution

1. Step 1: Understand cycle impact

   If the list has a cycle, naive traversal will loop infinitely, breaking the algorithm.

2. Step 2: Detect and handle cycle

   Use Floyd's cycle detection to identify cycle presence and length, then adjust logic to avoid infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cycle detection is prerequisite for safe traversal [OK]

Hint: Detect cycle first to avoid infinite loops [OK]

Common Mistakes:

• Assuming list always terminates
• Using stack without cycle check
• Increasing n arbitrarily