🔗 Linked Lists: Core Operations

The Train Analogy 🚂

Imagine a train with many carriages. Each carriage holds passengers (data) and has a connector to the next carriage. That’s exactly what a linked list is!

Unlike an array (a row of numbered lockers), a linked list is like a treasure hunt. Each clue tells you where to find the next one!

1. Singly Linked List

What Is It?

A singly linked list is a chain of boxes. Each box has:

• Data (what’s inside the box)
• Next pointer (an arrow pointing to the next box)

The last box points to nothing (None). That’s how we know it’s the end!

graph LR
    A[Head: 10] --> B[20] --> C[30] --> D[None]

Simple Example

Think of kids holding hands in a line. Each kid knows who’s next, but not who’s behind them!

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

Real Life

• Music playlist: each song knows the next song
• Browser history: each page links to the previous one

Key Point

You can only walk forward. To find something, start from the head and follow the arrows!

2. Sentinel and Dummy Node Pattern

What Is It?

A dummy node (also called sentinel) is like a “fake” first box. It sits at the start but holds no real data.

Why? It makes your code simpler! You never have to check “Is the list empty?” or “Am I at the head?”

graph LR
    D["Dummy #40;fake#41;"] --> A[10] --> B[20] --> C[30]

Simple Example

Imagine a line at a theme park. There’s a sign saying “LINE STARTS HERE” before the first person. That sign is your dummy node!

def delete_value(head, val):
    dummy = Node(0)      # Fake node
    dummy.next = head    # Points to real list

    prev = dummy
    curr = head

    while curr:
        if curr.data == val:
            prev.next = curr.next
        else:
            prev = curr
        curr = curr.next

    return dummy.next    # Real head

Why Use It?

• No special case for empty list
• No special case for deleting the head
• Cleaner, less buggy code!

3. Floyd’s Cycle Detection 🐢🐇

What Is It?

How do you know if a linked list goes in circles? Use two runners!

• Slow pointer (turtle) 🐢: moves 1 step
• Fast pointer (rabbit) 🐇: moves 2 steps

If there’s a loop, the rabbit will eventually catch up to the turtle!

graph LR
    A[1] --> B[2] --> C[3] --> D[4]
    D --> B

Simple Example

Imagine running on a circular track. A faster runner will eventually lap the slower one. That’s how we detect cycles!

def has_cycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next       # 1 step
        fast = fast.next.next  # 2 steps

        if slow == fast:
            return True

    return False

Why It Works

• If no cycle: fast reaches the end
• If cycle: fast catches slow inside the loop

Fun Fact: This is also called the “Tortoise and Hare” algorithm!

4. Finding Middle of Linked List

What Is It?

Find the middle node without counting all nodes first!

Use the same two-pointer trick:

• Slow moves 1 step
• Fast moves 2 steps

When fast reaches the end, slow is at the middle!

graph LR
    A[1] --> B[2] --> C["3 #40;middle#41;"] --> D[4] --> E[5]

Simple Example

Two friends walk the same path. One walks twice as fast. When the fast friend finishes, the slow friend is halfway!

def find_middle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow  # This is middle!

Quick Math

• Fast travels 2× the distance
• When fast = end, slow = half
• Works for odd or even length lists!

5. Linked List Reversal 🔄

What Is It?

Flip the entire list so the last node becomes first!

Before: 1 → 2 → 3 → None After: 3 → 2 → 1 → None

Simple Example

Think of reversing a line of kids. The last kid becomes the leader, and everyone points to who was behind them!

def reverse_list(head):
    prev = None
    curr = head

    while curr:
        next_temp = curr.next  # Save next
        curr.next = prev       # Flip arrow
        prev = curr            # Move prev
        curr = next_temp       # Move curr

    return prev  # New head

Step by Step

graph TD
    A["Step 1: 1 → 2 → 3"] --> B["Step 2: None ← 1 | 2 → 3"]
    B --> C["Step 3: None ← 1 ← 2 | 3"]
    C --> D["Step 4: None ← 1 ← 2 ← 3"]

Key Insight

We need 3 pointers:

• prev: where we came from
• curr: where we are
• next: where we’re going

6. Reverse Linked List II

What Is It?

Reverse only a portion of the list!

Given positions left and right, reverse nodes from position left to right.

Before: 1 → 2 → 3 → 4 → 5, left=2, right=4 After: 1 → 4 → 3 → 2 → 5

Simple Example

Imagine a line of 5 kids. You only want kids 2, 3, and 4 to swap order. Kid 1 and kid 5 stay in place!

def reverse_between(head, left, right):
    dummy = Node(0)
    dummy.next = head
    prev = dummy

    # Move to position before left
    for _ in range(left - 1):
        prev = prev.next

    # Start reversing
    curr = prev.next
    for _ in range(right - left):
        temp = curr.next
        curr.next = temp.next
        temp.next = prev.next
        prev.next = temp

    return dummy.next

Visual

graph TD
    A["Before: 1 → 2 → 3 → 4 → 5"]
    A --> B["Reverse 2-4"]
    B --> C["After: 1 → 4 → 3 → 2 → 5"]

Why Dummy Node?

Makes edge cases easy (like reversing from position 1)!

7. Reverse Nodes in k-Group 💪

What Is It?

This is the boss level! Reverse the list in chunks of size k.

Before: 1 → 2 → 3 → 4 → 5, k=2 After: 2 → 1 → 4 → 3 → 5

Before: 1 → 2 → 3 → 4 → 5, k=3 After: 3 → 2 → 1 → 4 → 5

If remaining nodes are less than k, leave them as-is!

Simple Example

Kids in a line, grouped by 3. Each group of 3 reverses their order. Leftover kids (less than 3) stay as they are!

def reverse_k_group(head, k):
    dummy = Node(0)
    dummy.next = head
    prev_group = dummy

    while True:
        # Check if k nodes exist
        kth = get_kth(prev_group, k)
        if not kth:
            break

        group_next = kth.next

        # Reverse group
        prev, curr = kth.next, prev_group.next
        while curr != group_next:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp

        # Connect groups
        temp = prev_group.next
        prev_group.next = kth
        prev_group = temp

    return dummy.next

def get_kth(node, k):
    while node and k > 0:
        node = node.next
        k -= 1
    return node

Visual (k=2)

graph TD
    A["1 → 2 → 3 → 4 → 5"]
    A --> B["Group 1: 1,2 | Group 2: 3,4 | Left: 5"]
    B --> C["Reverse each group"]
    C --> D["2 → 1 → 4 → 3 → 5"]

Key Steps

1. Check if k nodes exist ahead
2. Reverse those k nodes
3. Reconnect with previous group
4. Move to next group
5. Repeat until done!

Summary: Your New Superpowers! 🦸

You Did It! 🎉

You now understand the core building blocks of linked lists!

Remember:

• Pointers are just arrows pointing to the next thing
• Dummy nodes make your life easier
• Two-pointer tricks solve many problems elegantly

Go build something amazing with your new knowledge! 🚀