← Back to Tutorial Index

Chapter 2: Linked Lists

Master linked list operations including traversal, reversal, fast/slow pointers, and cycle detection. Learn when and where to use each technique.

1. Linked List Fundamentals

📌 When and Where to Use

  • Dynamic size: When you need a data structure that can grow/shrink efficiently
  • Insertion/deletion: When frequent insertions/deletions are needed (O(1) at known position)
  • Memory efficiency: When you don't know the size in advance
  • Real-world example: Browser history (back/forward), undo/redo functionality, music playlists, or implementing stacks/queues

Linked List Structure

class ListNode:
    """Node in a singly linked list"""
    def __init__(self, val=0, next=None):
        # Step 1: Store the value
        self.val = val
        # Step 2: Store reference to next node
        # None means this is the last node (tail)
        self.next = next

Step-by-Step Explanation:

Step 1 - Value Storage: Each node stores a value (the data we care about).
Step 2 - Next Pointer: Each node has a reference to the next node. If next is None, it's the tail (last node).
Key Difference from Arrays: Arrays store elements contiguously in memory. Linked lists store elements anywhere, connected by pointers.

2. Reversing a Linked List

📌 When and Where to Use

  • Palindrome checking: Reverse and compare
  • Stack implementation: Using linked list as stack
  • Problem transformations: Many problems become easier with reversed list
  • Real-world example: Reversing a playlist, implementing undo functionality, or processing data in reverse order

Algorithm Explanation

To reverse a linked list, we need to reverse the direction of all next pointers. We do this iteratively by maintaining three pointers:

  • prev: The previous node (starts as None)
  • curr: The current node we're processing
  • next: The next node (we save it before breaking the link)

Example: Reverse Linked List

def reverse_list(head):
    """
    Reverse a singly linked list iteratively.
    
    Args:
        head: First node of the linked list
    
    Returns:
        New head of the reversed list
    """
    # Step 1: Initialize pointers
    # prev will become the new head (starts as None)
    prev = None
    # curr starts at the original head
    curr = head
    
    # Step 2: Iterate through the list
    while curr is not None:
        # Step 3: Save the next node
        # We need to save this because we're about to break the link
        next_node = curr.next
        
        # Step 4: Reverse the link
        # Point current node's next to previous node
        curr.next = prev
        
        # Step 5: Move pointers forward
        # prev moves to current position
        prev = curr
        # curr moves to next position (which we saved earlier)
        curr = next_node
    
    # Step 6: Return new head
    # prev is now pointing to the last node (which is the new head)
    return prev

Step-by-Step Code Walkthrough:

Step 1 - Initialize:
  • prev = None: Will eventually become the new head
  • curr = head: Start from the original head
Step 2 - Loop: Continue until we've processed all nodes (curr is not None).
Step 3 - Save Next: Before breaking the link, save curr.next in next_node. We'll need it to continue traversal.
Step 4 - Reverse Link: Point curr.next to prev. This reverses the direction of the arrow.
Step 5 - Advance: Move prev to curr and curr to next_node.
Step 6 - Return: When loop ends, prev points to the last node of original list, which is now the new head.

Visualization:

Original: 1 → 2 → 3 → 4 → None

After reversal: None ← 1 ← 2 ← 3 ← 4 (head)

Time Complexity:

O(n) - Visit each node once

Space Complexity:

O(1) - Only using constant extra space

3. Fast and Slow Pointers (Floyd's Cycle Detection)

📌 When and Where to Use

  • Cycle detection: Finding if linked list has a cycle
  • Middle element: Finding middle of linked list
  • Nth from end: Finding kth node from end
  • Real-world example: Detecting infinite loops in state machines, finding the middle of a playlist, or detecting circular references in data structures

Algorithm Explanation

Also known as "tortoise and hare" algorithm:

  • Slow pointer: Moves one step at a time
  • Fast pointer: Moves two steps at a time
  • Key insight: If there's a cycle, fast pointer will eventually catch up to slow pointer
  • If no cycle: Fast pointer reaches the end (None)

Example: Detect Cycle in Linked List

def has_cycle(head):
    """
    Detect if linked list has a cycle using Floyd's algorithm.
    
    Args:
        head: First node of the linked list
    
    Returns:
        True if cycle exists, False otherwise
    """
    # Step 1: Handle empty list
    if head is None:
        return False
    
    # Step 2: Initialize two pointers
    # slow moves one step at a time
    slow = head
    # fast moves two steps at a time
    fast = head
    
    # Step 3: Move pointers until they meet or fast reaches end
    while fast is not None and fast.next is not None:
        # Step 3a: Move slow pointer one step
        slow = slow.next
        
        # Step 3b: Move fast pointer two steps
        fast = fast.next.next
        
        # Step 3c: Check if they meet
        # If slow == fast, we have a cycle!
        if slow == fast:
            return True
    
    # Step 4: No cycle found
    # Fast pointer reached the end (None)
    return False

Step-by-Step Code Walkthrough:

Step 1 - Edge Case: If list is empty, no cycle exists.
Step 2 - Initialize: Both pointers start at head. They'll move at different speeds.
Step 3 - Loop: Continue while fast can move (fast and fast.next are not None).
  • Step 3a: Move slow one step → slow = slow.next
  • Step 3b: Move fast two steps → fast = fast.next.next
  • Step 3c: If they meet (slow == fast), cycle exists!
Why it works: If there's a cycle, fast will eventually enter it. Once both are in the cycle, fast (moving 2x speed) will catch up to slow.
Step 4 - No Cycle: If fast reaches None, there's no cycle.

Time Complexity:

O(n) - In worst case, fast pointer traverses the list once

Space Complexity:

O(1) - Only using two pointers

4. Finding Middle Element

Example: Middle of Linked List

def find_middle(head):
    """
    Find middle element of linked list using fast/slow pointers.
    
    Args:
        head: First node of the linked list
    
    Returns:
        Middle node (or second middle if even number of nodes)
    """
    # Step 1: Handle edge cases
    if head is None or head.next is None:
        return head
    
    # Step 2: Initialize two pointers
    slow = head
    fast = head
    
    # Step 3: Move pointers
    # When fast reaches end, slow will be at middle
    while fast is not None and fast.next is not None:
        # Step 3a: Slow moves one step
        slow = slow.next
        
        # Step 3b: Fast moves two steps
        fast = fast.next.next
    
    # Step 4: Return middle node
    # slow is now at the middle
    return slow

Step-by-Step Code Walkthrough:

Step 1 - Edge Cases: If list is empty or has one node, return head.
Step 2 - Initialize: Both start at head.
Step 3 - Move:
  • Slow moves 1 step per iteration
  • Fast moves 2 steps per iteration
  • When fast reaches end, slow is at middle!
Why it works: Fast covers twice the distance. When fast finishes, slow is halfway.
Step 4 - Return: Slow pointer is at the middle node.

Example:

List: 1 → 2 → 3 → 4 → 5

  • After iteration 1: slow=2, fast=3
  • After iteration 2: slow=3, fast=5
  • Fast.next is None → stop. Middle is 3

5. Merging Two Sorted Linked Lists

📌 When and Where to Use

  • Merge operations: Combining two sorted lists into one
  • Merge sort: Part of merge sort algorithm for linked lists
  • Real-world example: Merging two sorted playlists, combining sorted transaction logs, or merging sorted user lists

Example: Merge Two Sorted Lists

def merge_two_lists(list1, list2):
    """
    Merge two sorted linked lists into one sorted list.
    
    Args:
        list1: Head of first sorted linked list
        list2: Head of second sorted linked list
    
    Returns:
        Head of merged sorted linked list
    """
    # Step 1: Create dummy node
    # This simplifies the code by avoiding special cases for head
    dummy = ListNode(0)
    # current tracks where we are in the merged list
    current = dummy
    
    # Step 2: Compare and merge
    # Continue while both lists have nodes
    while list1 is not None and list2 is not None:
        # Step 2a: Compare values
        if list1.val <= list2.val:
            # list1's value is smaller or equal
            # Step 2b: Add list1's node to merged list
            current.next = list1
            # Step 2c: Move list1 pointer forward
            list1 = list1.next
        else:
            # list2's value is smaller
            # Step 2d: Add list2's node to merged list
            current.next = list2
            # Step 2e: Move list2 pointer forward
            list2 = list2.next
        
        # Step 2f: Move current pointer forward
        current = current.next
    
    # Step 3: Append remaining nodes
    # One list is exhausted, append the other
    if list1 is not None:
        current.next = list1
    else:
        current.next = list2
    
    # Step 4: Return merged list
    # dummy.next is the actual head (skip dummy node)
    return dummy.next

Step-by-Step Code Walkthrough:

Step 1 - Dummy Node: Create a dummy node to simplify code. We'll build the merged list starting from dummy.next.
Step 2 - Compare and Merge: While both lists have nodes:
  • Step 2a: Compare values at current positions
  • Step 2b/2d: Add the smaller node to merged list
  • Step 2c/2e: Move the pointer of the list we took from
  • Step 2f: Move current pointer forward
Step 3 - Append Remaining: When one list is exhausted, append the rest of the other list (it's already sorted).
Step 4 - Return: Return dummy.next (the actual head, skipping the dummy).

Example:

list1: 1 → 3 → 5

list2: 2 → 4 → 6

Result: 1 → 2 → 3 → 4 → 5 → 6

Time Complexity:

O(n + m) - Visit each node once

Space Complexity:

O(1) - Only using constant extra space (dummy node)

📚 Chapter Summary

  • Reversal: Use three pointers (prev, curr, next) to reverse links iteratively
  • Fast/Slow Pointers: Use for cycle detection, finding middle, or nth from end
  • Merging: Compare nodes from both lists and build merged list incrementally
  • Key Insight: Linked lists require careful pointer management - always save next before modifying

Key Takeaway: Most linked list problems can be solved with pointer manipulation. The trick is maintaining references correctly and handling edge cases (empty list, single node, etc.).

← Previous: Chapter 8 Next: Chapter 10 - Bit Manipulation →