Palindrome Linked List

🎯

Palindrome Linked List

easyTWO_POINTERAmazonFacebookMicrosoft

Imagine you have a chain of beads and want to check if the sequence of colors reads the same forwards and backwards without rearranging them.

💡 This problem tests your understanding of linked lists and two-pointer techniques. Beginners often struggle because linked lists don't allow direct indexing, making it tricky to compare elements from both ends efficiently.

📋

Problem Statement

Given the head of a singly linked list, determine if the linked list is a palindrome. Return true if it is, and false otherwise.

1 ≤ n ≤ 10^5Node values are integersExpected time complexity: O(n)Expected space complexity: O(1) or O(n) depending on approach

💡

Example

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

Outputtrue

The list reads the same forwards and backwards.

Input"head = [1, 2]"

Outputfalse

The list is not the same forwards and backwards.

• Single node list → true
• List with all identical elements → true
• List with two different elements → false
• Empty list (if allowed) → true

⚠️

Common Mistakes

Not handling odd length lists correctly

Incorrect comparison leading to false negatives

✅ Skip the middle element when list length is odd before comparison

Not restoring the list after reversing second half

Modifies input list unexpectedly, which may cause issues in real applications

✅ Reverse the second half again after comparison to restore original list

Using extra space unnecessarily in optimal approach

Fails to meet O(1) space requirement

✅ Avoid stacks or arrays; reverse second half in place instead

Incorrectly finding the midpoint with fast and slow pointers

Leads to wrong half being reversed or compared

✅ Advance fast pointer by two steps and slow by one until fast reaches end

Not checking for empty or single node lists

Code may crash or return wrong result

✅ Add base case checks for empty or single node lists returning true

🧠

Brute Force (Using Array Conversion)

💡 This approach exists to build intuition by simplifying the problem to array palindrome checking, which is easier to understand and implement for beginners.

Intuition

Convert the linked list into an array and then check if the array is a palindrome by comparing elements from both ends.

Algorithm

1. Traverse the linked list and copy all node values into an array.
2. Use two pointers, one at the start and one at the end of the array.
3. Compare elements at these pointers; if they differ, return false.
4. If all pairs match, return true.

💡 This algorithm is straightforward but requires extra space. It helps beginners understand the palindrome concept before optimizing.

</>

Code

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

def isPalindrome(head):
    vals = []
    current = head
    while current:
        vals.append(current.val)
        current = current.next
    left, right = 0, len(vals) - 1
    while left < right:
        if vals[left] != vals[right]:
            return False
        left += 1
        right -= 1
    return True

# Example usage:
if __name__ == '__main__':
    # Create linked list 1->2->2->1
    node4 = ListNode(1)
    node3 = ListNode(2, node4)
    node2 = ListNode(2, node3)
    node1 = ListNode(1, node2)
    print(isPalindrome(node1))  # Output: True

Line Notes

vals = []Initialize an empty list to store node values for easy access.

while current:Traverse the linked list to collect all values.

if vals[left] != vals[right]:Check if the current pair of elements differ, indicating not a palindrome.

return TrueIf all pairs match, confirm the list is a palindrome.

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

public class Solution {
    public boolean isPalindrome(ListNode head) {
        ArrayList<Integer> vals = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            vals.add(current.val);
            current = current.next;
        }
        int left = 0, right = vals.size() - 1;
        while (left < right) {
            if (!vals.get(left).equals(vals.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode node4 = new ListNode(1);
        ListNode node3 = new ListNode(2); node3.next = node4;
        ListNode node2 = new ListNode(2); node2.next = node3;
        ListNode node1 = new ListNode(1); node1.next = node2;
        Solution sol = new Solution();
        System.out.println(sol.isPalindrome(node1)); // true
    }
}

Line Notes

ArrayList<Integer> vals = new ArrayList<>();Use dynamic array to store node values for random access.

while (current != null)Traverse the linked list to collect values.

if (!vals.get(left).equals(vals.get(right)))Compare elements from both ends to check palindrome property.

return true;Return true if all pairs match, confirming palindrome.

#include <iostream>
#include <vector>
using namespace std;

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

bool isPalindrome(ListNode* head) {
    vector<int> vals;
    ListNode* current = head;
    while (current != nullptr) {
        vals.push_back(current->val);
        current = current->next;
    }
    int left = 0, right = vals.size() - 1;
    while (left < right) {
        if (vals[left] != vals[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    ListNode* node4 = new ListNode(1);
    ListNode* node3 = new ListNode(2); node3->next = node4;
    ListNode* node2 = new ListNode(2); node2->next = node3;
    ListNode* node1 = new ListNode(1); node1->next = node2;
    cout << (isPalindrome(node1) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

vector<int> vals;Store node values in a vector for indexed access.

while (current != nullptr)Traverse linked list to collect values.

if (vals[left] != vals[right])Compare elements from both ends to detect mismatch.

return true;Return true if no mismatches found, confirming palindrome.

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

function isPalindrome(head) {
    const vals = [];
    let current = head;
    while (current !== null) {
        vals.push(current.val);
        current = current.next;
    }
    let left = 0, right = vals.length - 1;
    while (left < right) {
        if (vals[left] !== vals[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

// Example usage:
const node4 = new ListNode(1);
const node3 = new ListNode(2, node4);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);
console.log(isPalindrome(node1)); // true

Line Notes

const vals = [];Create an array to hold node values for easy palindrome check.

while (current !== null)Traverse the linked list to collect all values.

if (vals[left] !== vals[right])Check if current pair of values differ, indicating not palindrome.

return true;Return true if all pairs match, confirming palindrome.

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse the list once to copy values (O(n)) and then check palindrome in O(n). Extra space is used for the array of size n.

💡 For n=100,000 nodes, this means 100,000 operations to copy and 100,000 to check, which is feasible but uses extra memory.

Interview Verdict: Accepted

This approach works but uses extra space, which might not be optimal for very large inputs.

🧠

Better (Fast & Slow Pointer + Stack)

💡 This approach improves space usage by only storing half the list's values, introducing the fast and slow pointer technique to find the midpoint.

Intuition

Use two pointers to find the middle of the list. Push the first half's values onto a stack, then compare the second half with the stack's top elements.

Algorithm

1. Initialize fast and slow pointers at head.
2. Move fast by two steps and slow by one step, pushing slow's values onto a stack.
3. When fast reaches the end, slow is at midpoint.
4. If list length is odd, skip the middle element.
5. Compare remaining list nodes with stack's top values.
6. If all match, return true; else false.

💡 This algorithm cleverly uses a stack to reverse the first half's values, enabling comparison without full array storage.

</>

Code

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

def isPalindrome(head):
    slow = fast = head
    stack = []
    while fast and fast.next:
        stack.append(slow.val)
        slow = slow.next
        fast = fast.next.next
    if fast:  # Odd length, skip middle
        slow = slow.next
    while slow:
        top = stack.pop()
        if top != slow.val:
            return False
        slow = slow.next
    return True

# Example usage:
if __name__ == '__main__':
    node4 = ListNode(1)
    node3 = ListNode(2, node4)
    node2 = ListNode(2, node3)
    node1 = ListNode(1, node2)
    print(isPalindrome(node1))  # Output: True

Line Notes

slow = fast = headInitialize two pointers to find midpoint efficiently.

while fast and fast.next:Advance fast by two and slow by one to find middle.

stack.append(slow.val)Store first half values to compare later.

if fast: # Odd length, skip middleSkip the middle element for odd-length lists.

import java.util.*;

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

public class Solution {
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            stack.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) { // Odd length
            slow = slow.next;
        }
        while (slow != null) {
            if (stack.pop() != slow.val) {
                return false;
            }
            slow = slow.next;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode node4 = new ListNode(1);
        ListNode node3 = new ListNode(2); node3.next = node4;
        ListNode node2 = new ListNode(2); node2.next = node3;
        ListNode node1 = new ListNode(1); node1.next = node2;
        Solution sol = new Solution();
        System.out.println(sol.isPalindrome(node1)); // true
    }
}

Line Notes

Stack<Integer> stack = new Stack<>();Use stack to store first half values for reverse comparison.

while (fast != null && fast.next != null)Move fast and slow pointers to find midpoint.

if (fast != null) { // Odd lengthSkip middle element for odd-length lists.

if (stack.pop() != slow.val)Compare second half values with stack top.

#include <iostream>
#include <stack>
using namespace std;

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

bool isPalindrome(ListNode* head) {
    stack<int> st;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        st.push(slow->val);
        slow = slow->next;
        fast = fast->next->next;
    }
    if (fast != nullptr) { // Odd length
        slow = slow->next;
    }
    while (slow != nullptr) {
        if (st.top() != slow->val) {
            return false;
        }
        st.pop();
        slow = slow->next;
    }
    return true;
}

int main() {
    ListNode* node4 = new ListNode(1);
    ListNode* node3 = new ListNode(2); node3->next = node4;
    ListNode* node2 = new ListNode(2); node2->next = node3;
    ListNode* node1 = new ListNode(1); node1->next = node2;
    cout << (isPalindrome(node1) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

stack<int> st;Stack stores first half values for reverse order comparison.

while (fast != nullptr && fast->next != nullptr)Find midpoint using fast and slow pointers.

if (fast != nullptr) { // Odd lengthSkip middle node for odd-length lists.

if (st.top() != slow->val)Compare second half nodes with stack top values.

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

function isPalindrome(head) {
    let slow = head, fast = head;
    const stack = [];
    while (fast !== null && fast.next !== null) {
        stack.push(slow.val);
        slow = slow.next;
        fast = fast.next.next;
    }
    if (fast !== null) { // Odd length
        slow = slow.next;
    }
    while (slow !== null) {
        if (stack.pop() !== slow.val) {
            return false;
        }
        slow = slow.next;
    }
    return true;
}

// Example usage:
const node4 = new ListNode(1);
const node3 = new ListNode(2, node4);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);
console.log(isPalindrome(node1)); // true

Line Notes

const stack = [];Stack holds first half values for reverse comparison.

while (fast !== null && fast.next !== null)Use fast and slow pointers to find midpoint.

if (fast !== null) { // Odd lengthSkip middle node for odd-length lists.

if (stack.pop() !== slow.val)Compare second half values with stack top.

⏱

Complexity

TimeO(n)

SpaceO(n/2) = O(n)

We traverse the list once to find midpoint and push half values onto stack, then compare second half in O(n). Space is reduced to half compared to brute force.

💡 For n=100,000, this means 50,000 values stored in stack, which is better but still uses extra memory.

Interview Verdict: Accepted

This approach is better than brute force in space but still not optimal for very large inputs.

🧠

Optimal (Reverse Second Half In-Place)

💡 This approach optimizes space by reversing the second half of the list in place, allowing direct comparison without extra memory.

Intuition

Find the middle of the list, reverse the second half in place, then compare the first half and reversed second half node by node.

Algorithm

1. Use fast and slow pointers to find the middle of the list.
2. Reverse the second half of the list starting from slow pointer.
3. Compare nodes from the start and from the reversed second half.
4. If all nodes match, the list is a palindrome.
5. Restore the list by reversing the second half again (optional).
6. Return the result.

💡 This algorithm is tricky because it modifies the list temporarily but uses constant space and linear time.

</>

Code

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

def reverse(head):
    prev = None
    current = head
    while current:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt
    return prev

def isPalindrome(head):
    if not head or not head.next:
        return True
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    second_half_start = reverse(slow)
    first_half_start = head
    second_half_copy = second_half_start
    result = True
    while second_half_start:
        if first_half_start.val != second_half_start.val:
            result = False
            break
        first_half_start = first_half_start.next
        second_half_start = second_half_start.next
    reverse(second_half_copy)  # Optional: restore list
    return result

# Example usage:
if __name__ == '__main__':
    node4 = ListNode(1)
    node3 = ListNode(2, node4)
    node2 = ListNode(2, node3)
    node1 = ListNode(1, node2)
    print(isPalindrome(node1))  # Output: True

Line Notes

def reverse(head):Helper function to reverse a linked list segment in place.

while fast and fast.next:Find midpoint using fast and slow pointers.

second_half_start = reverse(slow)Reverse second half starting from midpoint.

while second_half_start:Compare nodes from first half and reversed second half.

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

public class Solution {
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        return prev;
    }

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode secondHalfStart = reverse(slow);
        ListNode firstHalfStart = head;
        ListNode secondHalfCopy = secondHalfStart;
        boolean result = true;
        while (secondHalfStart != null) {
            if (firstHalfStart.val != secondHalfStart.val) {
                result = false;
                break;
            }
            firstHalfStart = firstHalfStart.next;
            secondHalfStart = secondHalfStart.next;
        }
        reverse(secondHalfCopy); // Optional restore
        return result;
    }

    public static void main(String[] args) {
        ListNode node4 = new ListNode(1);
        ListNode node3 = new ListNode(2); node3.next = node4;
        ListNode node2 = new ListNode(2); node2.next = node3;
        ListNode node1 = new ListNode(1); node1.next = node2;
        Solution sol = new Solution();
        System.out.println(sol.isPalindrome(node1)); // true
    }
}

Line Notes

private ListNode reverse(ListNode head)Reverse linked list segment in place to compare halves.

while (fast != null && fast.next != null)Find midpoint with fast and slow pointers.

ListNode secondHalfStart = reverse(slow);Reverse second half starting at midpoint.

while (secondHalfStart != null)Compare nodes from first half and reversed second half.

#include <iostream>
using namespace std;

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

ListNode* reverse(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* current = head;
    while (current != nullptr) {
        ListNode* nextTemp = current->next;
        current->next = prev;
        prev = current;
        current = nextTemp;
    }
    return prev;
}

bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* secondHalfStart = reverse(slow);
    ListNode* firstHalfStart = head;
    ListNode* secondHalfCopy = secondHalfStart;
    bool result = true;
    while (secondHalfStart) {
        if (firstHalfStart->val != secondHalfStart->val) {
            result = false;
            break;
        }
        firstHalfStart = firstHalfStart->next;
        secondHalfStart = secondHalfStart->next;
    }
    reverse(secondHalfCopy); // Optional restore
    return result;
}

int main() {
    ListNode* node4 = new ListNode(1);
    ListNode* node3 = new ListNode(2); node3->next = node4;
    ListNode* node2 = new ListNode(2); node2->next = node3;
    ListNode* node1 = new ListNode(1); node1->next = node2;
    cout << (isPalindrome(node1) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

ListNode* reverse(ListNode* head)Reverse linked list segment in place for comparison.

while (fast && fast->next)Find midpoint using fast and slow pointers.

ListNode* secondHalfStart = reverse(slow);Reverse second half starting at midpoint.

while (secondHalfStart)Compare nodes from first half and reversed second half.

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

function reverse(head) {
    let prev = null;
    let current = head;
    while (current !== null) {
        let nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }
    return prev;
}

function isPalindrome(head) {
    if (!head || !head.next) return true;
    let slow = head, fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let secondHalfStart = reverse(slow);
    let firstHalfStart = head;
    let secondHalfCopy = secondHalfStart;
    let result = true;
    while (secondHalfStart !== null) {
        if (firstHalfStart.val !== secondHalfStart.val) {
            result = false;
            break;
        }
        firstHalfStart = firstHalfStart.next;
        secondHalfStart = secondHalfStart.next;
    }
    reverse(secondHalfCopy); // Optional restore
    return result;
}

// Example usage:
const node4 = new ListNode(1);
const node3 = new ListNode(2, node4);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);
console.log(isPalindrome(node1)); // true

Line Notes

function reverse(head)Reverse linked list segment in place for direct comparison.

while (fast !== null && fast.next !== null)Find midpoint using fast and slow pointers.

let secondHalfStart = reverse(slow);Reverse second half starting at midpoint.

while (secondHalfStart !== null)Compare nodes from first half and reversed second half.

⏱

Complexity

TimeO(n)

SpaceO(1)

We traverse the list to find midpoint, reverse half in place, and compare nodes, all in linear time with constant extra space.

💡 For n=100,000, this means 100,000 operations but minimal memory usage, making it scalable.

Interview Verdict: Accepted

This is the best approach for interviews as it meets optimal time and space requirements.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the optimal in-place reversal approach impresses most, but understanding brute force and stack methods helps build intuition.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(n)	No	N/A	Mention only - never code
2. Fast & Slow Pointer + Stack	O(n)	O(n/2)	No	N/A	Good to mention as improvement, but not optimal
3. Reverse Second Half In-Place	O(n)	O(1)	No	Yes (optional)	Code this approach in 95% of interviews

💼

Interview Strategy

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

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach to show understanding.Step 3: Discuss improvements using fast and slow pointers with a stack.Step 4: Explain the optimal in-place reversal approach.Step 5: Code the optimal solution carefully and test edge cases.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Coding: 10min → Testing & optimization: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your grasp of linked list traversal, two-pointer technique, space-time tradeoffs, and ability to write clean, bug-free code.

Common Follow-ups

• What if you cannot modify the linked list? → Use stack approach.
• How to restore the list after checking? → Reverse second half again.
• What if the list is doubly linked? → Could compare from both ends directly.
• Can you do it recursively? → Yes, but watch for stack overflow.

💡 These follow-ups test your flexibility and deeper understanding of the problem constraints and variations.

🔍

Pattern Recognition

When to Use

1) Need to check palindrome property on linked list; 2) No direct indexing available; 3) Fast and slow pointers can find midpoint; 4) Reversing part of list is feasible.

Signature Phrases

'determine if linked list is palindrome''fast and slow pointers''reverse second half'

NOT This Pattern When

Problems that require full sorting or dynamic programming are different patterns.

Similar Problems

Palindrome Number - similar palindrome check but on integer digitsLinked List Cycle - uses fast and slow pointers to detect cycles

Practice

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

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

3. Identify the bug in the following code snippet intended to find the intersection node of two singly linked lists using the two-pointer approach:

medium

A. Line 6: Using '!=' instead of 'is not' to compare nodes

B. Line 8: Not checking if headA or headB is None before starting

C. Line 9: Incorrectly resetting pA and pB to headB and headA respectively

D. Line 10: Returning pA instead of pB

Solution

1. Step 1: Understand node comparison

   Nodes must be compared by reference, not by value. Using '!=' compares values, not references, causing incorrect intersection detection.

2. Step 2: Identify correct comparison operator

   'is not' compares object identity, ensuring correct detection of intersection node.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using '!=' causes false positives or misses intersection [OK]

Hint: Use 'is' or 'is not' to compare nodes, not '==' or '!=' [OK]

Common Mistakes:

• Comparing node values instead of references
• Forgetting to handle empty lists
• Infinite loops due to pointer reset errors

4. Suppose the problem is extended so that the input linked lists can be reused multiple times in different additions without modification. Which modification to the optimal recursive solution is necessary to ensure correctness and input integrity?

hard

A. Use stacks to simulate reverse traversal without modifying input lists or copying.

B. Create deep copies of input lists before padding and addition to avoid modifying original lists.

C. Modify the recursive function to add digits without padding or copying.

D. Reverse the input lists in-place before addition to simplify logic.

Solution

1. Step 1: Understand input reuse constraint

   Input lists must remain unmodified for reuse, so in-place reversal or padding that changes nodes is disallowed.

2. Step 2: Identify approach preserving input integrity

   Using stacks to simulate reverse traversal reads digits from least significant to most significant without modifying or copying the lists.

3. Step 3: Compare alternatives

   Reversing in-place breaks input reuse; copying is expensive; recursion without padding fails alignment.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stacks preserve input and allow correct addition [OK]

Hint: Stacks simulate reverse without input mutation [OK]

Common Mistakes:

• Reversing input lists modifies them
• Copying inputs is costly and unnecessary
• Ignoring alignment leads to wrong sums

5. Suppose the problem is modified so that the linked list is circular (the last node points back to the head). Which of the following modifications to the recursive swapPairs function correctly handles swapping nodes in pairs without causing infinite recursion or losing nodes?

hard

A. Modify the base case to stop recursion when the next node is the head, breaking the cycle.

B. Add a visited set to track nodes and stop recursion when a node repeats.

C. Use the same recursive approach without changes; it naturally terminates on circular lists.

D. Convert the circular list to a linear list by breaking the cycle before swapping.

Solution

1. Step 1: Understand circular list implications

   In a circular list, naive recursion never reaches a null node, causing infinite recursion.

2. Step 2: Modify base case to detect cycle

   Stopping recursion when next node is the head prevents infinite loops and preserves all nodes.

3. Step 3: Compare alternatives

   Using a visited set adds overhead; breaking cycle beforehand changes problem constraints; naive recursion fails.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Base case adjusted for cycle detection prevents infinite recursion [OK]

Hint: Detect cycle in base case to stop recursion [OK]

Common Mistakes:

• Ignoring cycle causes infinite recursion
• Trying naive recursion without cycle check