Linked List Problems

# CHAPTER 8

Linked List Problems #

1. Chapter Introduction #

2. The Structure of a Node #

// Standard representation
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

*Crucial Rule:* The only way to traverse a linked list is to start at the head and follow the next pointers. You cannot jump directly to the 5th element. Finding the 5th element is an O(N) Time operation. However, inserting a node between two known nodes is O(1) Time (you just rewire two pointers).

3. Pattern 1: Reversing a Linked List #

def reverseList(head):
    prev = None
    curr = head
    
    while curr:
        next_temp = curr.next # 1. Save the rest of the list
        curr.next = prev      # 2. REVERSE the pointer backwards
        prev = curr           # 3. Slide prev forward
        curr = next_temp      # 4. Slide curr forward
        
    return prev # prev becomes the new head of the reversed list
# Time: O(N), Space: O(1)

4. Pattern 2: Cycle Detection (Fast and Slow Pointers) #

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;          // 1 step
        fast = fast.next.next;     // 2 steps
        
        if (slow == fast) {
            return true; // Collision! Cycle detected.
        }
    }
    return false;
}

5. Pattern 3: The Dummy Node technique #

*Example: Merge Two Sorted Lists*

def mergeTwoLists(l1, l2):
    dummy = ListNode() # The fake starting node
    tail = dummy       # The pointer we use to build the new list
    
    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
        
    # Append whatever is left over
    if l1: tail.next = l1
    if l2: tail.next = l2
        
    return dummy.next # Return the true head

6. Real-World Scenario: Find the Middle Node #

7. Mini Project: Remove Nth Node From End #

1. 1. Place a Left and Right pointer at the dummy node.

1. 2. Move the Right pointer exactly N steps forward. (Creating a gap of size N).

1. 3. Now, move BOTH pointers forward 1 step at a time.

1. 4. When Right hits the end of the list, Left will be pointing exactly at the node *before* the one you need to delete!

1. 5. Delete it: Left.next = Left.next.next.

8. Common Mistakes #

• Null Pointer Exceptions: Trying to access curr.next.next without first checking if curr.next is null. Always check your bounds in the while loop condition.

• Losing the List: If you execute curr.next = prev before saving curr.next into a temporary variable, the entire rest of the linked list is lost in memory forever.

9. Best Practices #

• Draw it out: Never try to solve a Linked List pointer problem purely in your head. Draw 3 boxes with arrows on the whiteboard. When you write a line of code, erase the arrow and draw it pointing to the new box.

10. Exercises #

1. 1. Trace the reverseList code on paper using 3 boxes (A -> B -> C -> null).

1. 2. Why is the "Dummy Node" useful when removing nodes from a linked list?

11. MCQs #

14. Interview Questions #

• Q: "Given the head of a linked list and an integer val, remove all the nodes of the linked list that have Node.val == val, and return the new head." (LeetCode 203. Hint: Use a Dummy Node).

15. FAQs #

• Q: Does Java/Python have pointers?

16. Summary #

17. Next Chapter Recommendation #