Linked Lists

Core Concepts

Linked lists require careful pointer manipulation. Key techniques include:

• Dummy Nodes: Useful for edge cases when the head of the list might change.
• Fast & Slow Pointers (Tortoise and Hare): Used to find the middle of a list or detect cycles.
• In-place Reversal: Reversing the pointers of the nodes iteratively or recursively.

Cheatsheet Formulas

• Find Middle (Hare & Tortoise): slow = head, fast = head. Loop while fast and fast.next. Advance slow by 1, fast by 2.
• Detect Cycle: Same as finding middle. If slow == fast, there is a cycle.
• Reverse List: Needs 3 pointers: prev = null, curr = head, nextTemp = curr.next.
• Dummy Node: dummy = new Node(0), dummy.next = head. Return dummy.next. Prevents edge case headaches.

Classic Problem: Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
            
        return prev

Classic Problem: Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it using Floyd's Cycle-Finding Algorithm.

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                return true;
            }
        }
        
        return false;
    }
}

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
            
        slow = head
        fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                return True
                
        return False