Swap Nodes in Pairs

🎯

Swap Nodes in Pairs

mediumLINKED_LISTAmazonMicrosoft

Imagine you have a chain of train cars, and you want to swap every two adjacent cars to optimize loading. How would you do this efficiently without detaching the entire chain?

💡 This problem involves manipulating pointers in a linked list to swap nodes in pairs without creating new nodes or using extra space. Beginners often struggle because it requires careful pointer updates and understanding of linked list traversal, especially when swapping nodes in-place.

📋

Problem Statement

Given a singly linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed). Input: head of the linked list. Output: head of the modified list after swapping every two adjacent nodes.

The number of nodes in the list is in the range [1, 10^5].1 ≤ Node.val ≤ 1000

💡

Example

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

Output[2,1,4,3]

Swap nodes 1 and 2, then nodes 3 and 4.

Input"head = []"

Output[]

Empty list remains empty.

Input"head = [1]"

Output[1]

Single node list remains unchanged.

• Empty list → returns empty list
• Single node list → returns same single node
• List with odd number of nodes → last node remains in place
• List with two nodes → nodes swapped correctly

⚠️

Common Mistakes

Not handling the head swap correctly

The head pointer remains unchanged, resulting in incorrect output

✅ Use a dummy node to simplify head swaps

Incorrect pointer updates causing cycles or lost nodes

Infinite loops or missing nodes in output

✅ Carefully update next pointers in correct order

Forgetting to move the 'prev' pointer forward after swapping

Repeatedly swapping the same nodes or infinite loop

✅ Advance 'prev' to the last node of the swapped pair

Not handling odd-length lists properly

Last node gets lost or incorrectly swapped

✅ Check if at least two nodes exist before swapping

🧠

Brute Force (Recursive Swapping)

💡 Starting with recursion helps understand the problem by breaking it down into smaller subproblems. It’s intuitive but can lead to stack overflow for very large lists.

Intuition

Swap the first two nodes, then recursively swap the rest of the list. The base case is when there are fewer than two nodes left.

Algorithm

1. If the list is empty or has only one node, return it as is.
2. Swap the first two nodes by adjusting their next pointers.
3. Recursively call the function on the rest of the list starting from the third node.
4. Connect the swapped first pair to the result of the recursive call and return the new head.

💡 The recursion makes the problem easier to understand by focusing on just two nodes at a time, but keeping track of pointers is tricky.

</>

Code

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

def swapPairs(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    first_node = head
    second_node = head.next
    first_node.next = swapPairs(second_node.next)
    second_node.next = first_node
    return second_node

# Driver code to test
if __name__ == '__main__':
    # Create linked list 1->2->3->4
    n4 = ListNode(4)
    n3 = ListNode(3, n4)
    n2 = ListNode(2, n3)
    n1 = ListNode(1, n2)
    new_head = swapPairs(n1)
    # Print swapped list
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

if not head or not head.next:Base case: if fewer than two nodes, no swap needed

first_node = headIdentify the first node of the current pair

second_node = head.nextIdentify the second node of the current pair

first_node.next = swapPairs(second_node.next)Recursively swap the rest of the list and link to first node

second_node.next = first_nodeComplete the swap by pointing second node to first node

return second_nodeReturn new head of the swapped pair

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

public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode firstNode = head;
        ListNode secondNode = head.next;
        firstNode.next = swapPairs(secondNode.next);
        secondNode.next = firstNode;
        return secondNode;
    }

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

Line Notes

if (head == null || head.next == null) return head;Base case: no swap if less than two nodes

ListNode firstNode = head;Mark first node of pair

ListNode secondNode = head.next;Mark second node of pair

firstNode.next = swapPairs(secondNode.next);Recursively swap remaining list and link

secondNode.next = firstNode;Swap current pair by reversing pointers

return secondNode;Return new head after swap

#include <iostream>
using namespace std;

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

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* firstNode = head;
        ListNode* secondNode = head->next;
        firstNode->next = swapPairs(secondNode->next);
        secondNode->next = firstNode;
        return secondNode;
    }
};

int main() {
    ListNode* n4 = new ListNode(4);
    ListNode* n3 = new ListNode(3); n3->next = n4;
    ListNode* n2 = new ListNode(2); n2->next = n3;
    ListNode* n1 = new ListNode(1); n1->next = n2;
    Solution sol;
    ListNode* newHead = sol.swapPairs(n1);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

if (!head || !head->next) return head;Base case: stop recursion if less than two nodes

ListNode* firstNode = head;First node in current pair

ListNode* secondNode = head->next;Second node in current pair

firstNode->next = swapPairs(secondNode->next);Recursively swap rest and link to first node

secondNode->next = firstNode;Swap pointers to reverse current pair

return secondNode;Return new head of swapped pair

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

function swapPairs(head) {
    if (!head || !head.next) return head;
    let firstNode = head;
    let secondNode = head.next;
    firstNode.next = swapPairs(secondNode.next);
    secondNode.next = firstNode;
    return secondNode;
}

// Driver code
const n4 = new ListNode(4);
const n3 = new ListNode(3, n4);
const n2 = new ListNode(2, n3);
const n1 = new ListNode(1, n2);
const newHead = swapPairs(n1);
let curr = newHead;
while (curr) {
    console.log(curr.val);
    curr = curr.next;
}

Line Notes

if (!head || !head.next) return head;Base case: no swap if fewer than two nodes

let firstNode = head;Identify first node of pair

let secondNode = head.next;Identify second node of pair

firstNode.next = swapPairs(secondNode.next);Recursively swap rest and link to first node

secondNode.next = firstNode;Swap pointers to reverse current pair

return secondNode;Return new head after swap

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once, but recursion adds call stack overhead proportional to n/2 pairs.

💡 For n=20, about 20 operations plus 10 recursive calls on the stack.

Interview Verdict: Accepted but not optimal for very large lists due to recursion depth

Recursion is elegant but risks stack overflow; good for understanding but not always practical.

🧠

Iterative Approach with Dummy Node

💡 Iteration avoids recursion stack overflow and is more efficient in practice. Using a dummy node simplifies edge cases like swapping the head.

Intuition

Use a dummy node before the head to handle swaps uniformly. Iterate through the list, swapping pairs by adjusting pointers iteratively.

Algorithm

1. Create a dummy node pointing to head.
2. Initialize a pointer 'prev' to dummy.
3. While there are at least two nodes ahead, swap the next two nodes.
4. Move 'prev' pointer two nodes ahead after each swap.
5. Return dummy.next as the new head.

💡 The dummy node helps avoid special cases for the head, and pointer updates must be done carefully to maintain list integrity.

</>

Code

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

def swapPairs(head: ListNode) -> ListNode:
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
    while prev.next and prev.next.next:
        first = prev.next
        second = prev.next.next
        prev.next = second
        first.next = second.next
        second.next = first
        prev = first
    return dummy.next

# Driver code
if __name__ == '__main__':
    n4 = ListNode(4)
    n3 = ListNode(3, n4)
    n2 = ListNode(2, n3)
    n1 = ListNode(1, n2)
    new_head = swapPairs(n1)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

dummy = ListNode(0)Create dummy node to simplify head swaps

dummy.next = headPoint dummy to original head

prev = dummyInitialize prev pointer before head

while prev.next and prev.next.next:Loop while at least two nodes remain to swap

first = prev.nextFirst node in current pair

second = prev.next.nextSecond node in current pair

prev.next = secondLink prev to second node to start swap

first.next = second.nextLink first node to node after second

second.next = firstComplete swap by linking second to first

prev = firstMove prev pointer forward for next swap

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

public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        while (prev.next != null && prev.next.next != null) {
            ListNode first = prev.next;
            ListNode second = prev.next.next;
            prev.next = second;
            first.next = second.next;
            second.next = first;
            prev = first;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode n4 = new ListNode(4);
        ListNode n3 = new ListNode(3); n3.next = n4;
        ListNode n2 = new ListNode(2); n2.next = n3;
        ListNode n1 = new ListNode(1); n1.next = n2;
        Solution sol = new Solution();
        ListNode newHead = sol.swapPairs(n1);
        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 head swaps uniformly

dummy.next = head;Point dummy to original list head

ListNode prev = dummy;Prev pointer starts before head

while (prev.next != null && prev.next.next != null)Loop while pairs exist to swap

ListNode first = prev.next;First node of pair

ListNode second = prev.next.next;Second node of pair

prev.next = second;Link prev to second node to start swap

first.next = second.next;Link first node to node after second

second.next = first;Complete swap by linking second to first

prev = first;Move prev pointer forward

#include <iostream>
using namespace std;

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

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;
        while (prev->next && prev->next->next) {
            ListNode* first = prev->next;
            ListNode* second = prev->next->next;
            prev->next = second;
            first->next = second->next;
            second->next = first;
            prev = first;
        }
        return dummy.next;
    }
};

int main() {
    ListNode* n4 = new ListNode(4);
    ListNode* n3 = new ListNode(3); n3->next = n4;
    ListNode* n2 = new ListNode(2); n2->next = n3;
    ListNode* n1 = new ListNode(1); n1->next = n2;
    Solution sol;
    ListNode* newHead = sol.swapPairs(n1);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

ListNode dummy(0);Dummy node to simplify head swaps

dummy.next = head;Point dummy to original head

ListNode* prev = &dummy;Prev pointer before head

while (prev->next && prev->next->next)Loop while pairs exist

ListNode* first = prev->next;First node of pair

ListNode* second = prev->next->next;Second node of pair

prev->next = second;Link prev to second node

first->next = second->next;Link first node to node after second

second->next = first;Complete swap

prev = first;Move prev forward

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

function swapPairs(head) {
    let dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    while (prev.next && prev.next.next) {
        let first = prev.next;
        let second = prev.next.next;
        prev.next = second;
        first.next = second.next;
        second.next = first;
        prev = first;
    }
    return dummy.next;
}

// Driver code
const n4 = new ListNode(4);
const n3 = new ListNode(3, n4);
const n2 = new ListNode(2, n3);
const n1 = new ListNode(1, n2);
const newHead = swapPairs(n1);
let curr = newHead;
while (curr) {
    console.log(curr.val);
    curr = curr.next;
}

Line Notes

let dummy = new ListNode(0);Dummy node to handle head swaps

dummy.next = head;Point dummy to original list head

let prev = dummy;Prev pointer before head

while (prev.next && prev.next.next)Loop while pairs exist

let first = prev.next;First node of pair

let second = prev.next.next;Second node of pair

prev.next = second;Link prev to second node

first.next = second.next;Link first node to node after second

second.next = first;Complete swap

prev = first;Move prev forward

⏱

Complexity

TimeO(n)

SpaceO(1)

Each node is visited once, and no extra stack space is used.

💡 For n=20, about 20 operations and constant extra space, making it efficient.

Interview Verdict: Accepted and preferred for large inputs

Iterative approach is robust and efficient, suitable for production code.

🧠

Recursive Approach with Tail Recursion Optimization (Conceptual)

💡 Tail recursion can be optimized by some compilers/interpreters to avoid stack overflow, combining recursion clarity with iteration efficiency.

Intuition

Rewrite the recursive solution so that the recursive call is the last operation, enabling tail call optimization.

Algorithm

1. Check base case for fewer than two nodes.
2. Swap first two nodes.
3. Tail-recursively call swapPairs on the rest and link.
4. Return new head after swap.

💡 Tail recursion is a subtle optimization that requires understanding how recursion stacks work.

</>

Code

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

def swapPairs(head: ListNode) -> ListNode:
    def helper(node):
        if not node or not node.next:
            return node
        first = node
        second = node.next
        first.next = helper(second.next)
        second.next = first
        return second
    return helper(head)

# Driver code
if __name__ == '__main__':
    n4 = ListNode(4)
    n3 = ListNode(3, n4)
    n2 = ListNode(2, n3)
    n1 = ListNode(1, n2)
    new_head = swapPairs(n1)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

def helper(node):Inner function to enable tail recursion

if not node or not node.next:Base case for recursion

first = nodeFirst node in pair

second = node.nextSecond node in pair

first.next = helper(second.next)Tail recursive call for rest of list

second.next = firstSwap current pair

return secondReturn new head after swap

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

public class Solution {
    public ListNode swapPairs(ListNode head) {
        return helper(head);
    }

    private ListNode helper(ListNode node) {
        if (node == null || node.next == null) return node;
        ListNode first = node;
        ListNode second = node.next;
        first.next = helper(second.next);
        second.next = first;
        return second;
    }

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

Line Notes

return helper(head);Start recursion with helper function

private ListNode helper(ListNode node) {Helper function for tail recursion

if (node == null || node.next == null) return node;Base case

ListNode first = node;First node in pair

ListNode second = node.next;Second node in pair

first.next = helper(second.next);Tail recursive call

second.next = first;Swap nodes

return second;Return new head

#include <iostream>
using namespace std;

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

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        return helper(head);
    }

private:
    ListNode* helper(ListNode* node) {
        if (!node || !node->next) return node;
        ListNode* first = node;
        ListNode* second = node->next;
        first->next = helper(second->next);
        second->next = first;
        return second;
    }
};

int main() {
    ListNode* n4 = new ListNode(4);
    ListNode* n3 = new ListNode(3); n3->next = n4;
    ListNode* n2 = new ListNode(2); n2->next = n3;
    ListNode* n1 = new ListNode(1); n1->next = n2;
    Solution sol;
    ListNode* newHead = sol.swapPairs(n1);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

return helper(head);Start recursion with helper

ListNode* helper(ListNode* node) {Helper function for tail recursion

if (!node || !node->next) return node;Base case

ListNode* first = node;First node in pair

ListNode* second = node->next;Second node in pair

first->next = helper(second->next);Tail recursive call

second->next = first;Swap nodes

return second;Return new head

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

function swapPairs(head) {
    function helper(node) {
        if (!node || !node.next) return node;
        let first = node;
        let second = node.next;
        first.next = helper(second.next);
        second.next = first;
        return second;
    }
    return helper(head);
}

// Driver code
const n4 = new ListNode(4);
const n3 = new ListNode(3, n4);
const n2 = new ListNode(2, n3);
const n1 = new ListNode(1, n2);
const newHead = swapPairs(n1);
let curr = newHead;
while (curr) {
    console.log(curr.val);
    curr = curr.next;
}

Line Notes

function helper(node) {Inner helper for tail recursion

if (!node || !node.next) return node;Base case

let first = node;First node in pair

let second = node.next;Second node in pair

first.next = helper(second.next);Tail recursive call

second.next = first;Swap nodes

return second;Return new head

⏱

Complexity

TimeO(n)

SpaceO(n) due to recursion stack

Same as basic recursion, but tail recursion can be optimized in some languages.

💡 Tail recursion reduces overhead but still uses stack frames unless optimized.

Interview Verdict: Accepted, conceptual improvement but depends on language support

Tail recursion is a good concept but not always practical in all languages.

📊

All Approaches - One-Glance Tradeoffs

💡 Iterative approach with dummy node is the best choice for interviews due to efficiency and robustness.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive)	O(n)	O(n) due to recursion stack	Yes (deep recursion)	N/A	Good to explain logic, but avoid coding for large inputs
2. Iterative with Dummy Node	O(n)	O(1)	No	N/A	Preferred approach to code in interviews
3. Tail Recursion (Conceptual)	O(n)	O(n) unless optimized	Depends on language	N/A	Mention as optimization, rarely code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force recursive approach, followed by iterative optimization. Practice coding and testing edge cases.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force recursive approach to show understanding.Step 3: Explain the iterative approach with a dummy node for optimization.Step 4: Code the iterative solution carefully, explaining pointer updates.Step 5: Test with edge cases and discuss time/space complexity.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your understanding of linked list pointer manipulation, ability to handle edge cases, and optimization from recursion to iteration.

Common Follow-ups

• What if you want to swap nodes in groups of k instead of pairs? → Use a similar approach with k-group reversal.
• Can you do this without recursion or extra space? → Yes, iterative with dummy node is optimal.

💡 Follow-ups test your ability to generalize the solution and optimize space/time.

🔍

Pattern Recognition

When to Use

1) Problem involves linked list node rearrangement; 2) Swapping or reversing nodes in groups of fixed size; 3) Constraints forbid changing node values; 4) Requires in-place pointer manipulation.

Signature Phrases

swap every two adjacent nodeswithout modifying node valuesin-place linked list manipulation

NOT This Pattern When

Problems that only require changing node values or do not require in-place pointer changes

Similar Problems

Reverse Nodes in k-Group - generalizes swapping pairs to k nodesReverse Linked List - simpler reversal patternSwap Nodes in k-Group - similar pointer manipulation with groups

Practice

1. Consider the following Python code implementing the recursive two-pointer palindrome check for a linked list. Given the linked list 1 -> 2 -> 2 -> 1, what is the final return value of the function isPalindrome?

easy

A. False

B. Raises an exception

C. True

D. None

Solution

1. Step 1: Trace recursion to the end of the list

   The recursion reaches the last node (value 1), then unwinds comparing front and current nodes.

2. Step 2: Compare front and current nodes on unwind

   Comparisons: front=1 vs current=1 (match), front moves to 2; front=2 vs current=2 (match), front moves to 2; front=2 vs current=2 (match), front moves to 1; front=1 vs current=1 (match). All match, so returns True.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   All node pairs match, so palindrome check returns True [OK]

Hint: Recursive check compares front and back nodes symmetrically [OK]

Common Mistakes:

• Confusing return value with None
• Off-by-one in recursion causing False
• Assuming exception on empty or single node

2. Consider the following code snippet implementing the merge function used in bottom-up merge sort on linked lists. Given two sorted linked lists l1 and l2 with values l1: 1 -> 4 and l2: 2 -> 3, what is the resulting merged list after calling merge(l1, l2)?

easy

A. 1 -> 2 -> 4 -> 3

B. 1 -> 2 -> 3 -> 4

C. 2 -> 3 -> 1 -> 4

D. 1 -> 4 -> 2 -> 3

Solution

1. Step 1: Compare first nodes of l1 and l2

   l1.val=1, l2.val=2, 1 < 2, so add 1 to merged list and move l1 forward.

2. Step 2: Continue merging remaining nodes

   Now l1.val=4, l2.val=2, 2 < 4, add 2, move l2 forward; then 3 < 4, add 3, move l2 forward; l2 is null, append remaining l1 node 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Result is sorted merged list 1 -> 2 -> 3 -> 4 [OK]

Hint: Merge picks smaller node each step, preserving order [OK]

Common Mistakes:

• Appending entire l2 before l1 without comparison
• Not updating tail pointer correctly
• Confusing order of nodes after merge

3. What is the time complexity of the two-pointer length equalization approach to find the intersection node of two singly linked lists with lengths m and n, respectively?

medium

A. O(m + n)

B. O(m * n)

C. O(max(m, n) * 2)

D. O(m + n + k), where k is the length of the intersection

Solution

1. Step 1: Identify loop iterations

   Each pointer traverses its list once, then switches to the other list, traversing at most m + n nodes.

2. Step 2: Simplify complexity

   Total steps are proportional to m + n, so time complexity is O(m + n). O(m * n) is brute force, O(max(m, n) * 2) simplifies to O(m + n), and O(m + n + k) adds an unnecessary term.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer approach is linear in combined list lengths [OK]

Hint: Pointers traverse each list once plus switch [OK]

Common Mistakes:

• Confusing nested loops with two-pointer approach
• Counting intersection length separately
• Misreading max(m,n) as multiplication

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