🔗 Linked Lists: The Train of Data

Imagine a train where each car knows only about the next car. That’s a linked list!

🚂 What is a Linked List?

Picture a conga line at a party. Each person holds onto the shoulders of the person in front. Nobody can see the whole line, but everyone knows who’s next!

That’s a Singly Linked List:

• Each person = a Node
• Holding shoulders = the Next pointer
• The first person = the Head
• The last person (holding nothing) = Tail (points to null)

class Node {
    int data;      // What you're holding
    Node next;     // Who's in front of you

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

graph LR
    HEAD["🧑 Head"] --> A["📦 10"]
    A --> B["📦 20"]
    B --> C["📦 30"]
    C --> NULL["❌ null"]

Why Use Linked Lists?

🛡️ Sentinel and Dummy Node Pattern

The Problem

When adding or removing the first node, you need special code:

// Messy! Different logic for head
if (head == null) {
    head = newNode;
} else {
    // find position...
}

The Solution: Dummy Node

Put a fake guard at the front! This guard never leaves—it just points to the real first node.

// Create dummy (sentinel) node
Node dummy = new Node(-1);
dummy.next = head;

Think of it like a bouncer at a club. He’s always there, but he’s not actually part of the party!

graph LR
    DUMMY["🛡️ Dummy"] --> A["📦 10"]
    A --> B["📦 20"]
    B --> NULL["❌ null"]

Magic of Dummy Nodes

Before (messy):

if (head.val == target) {
    head = head.next;
} else {
    Node prev = head;
    // find and delete...
}

After (clean):

Node dummy = new Node(0);
dummy.next = head;
Node prev = dummy;
// Same logic works for ALL cases!
return dummy.next; // Real head

Rule: When in doubt, use a dummy node!

🐢🐇 Floyd’s Cycle Detection

The Mystery

How do you know if a train track loops back on itself?

You can’t just walk forever—you might never stop!

The Clever Solution

Send two runners:

• 🐢 Tortoise: Moves 1 step at a time
• 🐇 Hare: Moves 2 steps at a time

If there’s a loop, the fast runner will lap the slow one!

boolean hasCycle(Node head) {
    Node slow = head;
    Node fast = head;

    while (fast != null &&
           fast.next != null) {
        slow = slow.next;      // 1 step
        fast = fast.next.next; // 2 steps

        if (slow == fast) {
            return true; // They met! Loop!
        }
    }
    return false; // Fast hit the end
}

graph LR
    A["📦 1"] --> B["📦 2"]
    B --> C["📦 3"]
    C --> D["📦 4"]
    D --> B
    style D fill:#ff6b6b

Why Does This Work?

Imagine a circular track:

• If you run twice as fast as me
• You’ll catch up by 1 step each round
• Eventually, you MUST hit me!

Time: O(n) | Space: O(1)

🎯 Finding the Middle of a Linked List

The Challenge

Without knowing the length, how do you find the middle?

Same Trick: Fast & Slow Pointers!

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

Node findMiddle(Node head) {
    Node slow = head;
    Node fast = head;

    while (fast != null &&
           fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow; // Middle!
}

Visualization:

Start:  [1] [2] [3] [4] [5]
         S
         F

Step 1: [1] [2] [3] [4] [5]
             S
                 F

Step 2: [1] [2] [3] [4] [5]
                 S
                         F

Fast is done! Slow = Middle = 3

Even Length: Returns second middle node

[1] [2] [3] [4]  →  Returns 3

🔄 Linked List Reversal

The Classic Problem

Turn 1 → 2 → 3 → null into 3 → 2 → 1 → null

Think of it Like…

People in a conga line turning around one by one:

1. Each person lets go of the person in front
2. Grabs the person behind
3. Now facing the other way!

The Three-Pointer Dance

Node reverse(Node head) {
    Node prev = null;
    Node curr = head;

    while (curr != null) {
        Node next = curr.next; // Save
        curr.next = prev;      // Flip!
        prev = curr;           // Move
        curr = next;           // Move
    }

    return prev; // New head
}

Step-by-step:

Original: null ← [1] → [2] → [3] → null
                 prev  curr

Step 1:   null ← [1]   [2] → [3] → null
                 prev  curr

Step 2:   null ← [1] ← [2]   [3] → null
                       prev  curr

Step 3:   null ← [1] ← [2] ← [3]   null
                             prev  curr

Done! Return prev = [3]

🎭 Reverse Linked List II

The Twist

Reverse only part of the list!

Example:

Input:  1 → 2 → 3 → 4 → 5
Reverse from position 2 to 4
Output: 1 → 4 → 3 → 2 → 5

The Strategy

1. Walk to position before the start
2. Reverse the middle section
3. Reconnect the ends

Node reverseBetween(Node head,
                    int left, int right) {
    Node dummy = new Node(0);
    dummy.next = head;
    Node prev = dummy;

    // Step 1: Walk to left-1
    for (int i = 1; i < left; i++) {
        prev = prev.next;
    }

    // Step 2: Reverse [left, right]
    Node curr = prev.next;
    for (int i = 0; i < right - left; i++) {
        Node next = curr.next;
        curr.next = next.next;
        next.next = prev.next;
        prev.next = next;
    }

    return dummy.next;
}

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

🎪 Reverse Nodes in k-Group

The Grand Challenge

Reverse nodes in groups of k!

Example (k=3):

Input:  1 → 2 → 3 → 4 → 5 → 6 → 7
Output: 3 → 2 → 1 → 6 → 5 → 4 → 7
        \_______/   \_______/   ↑
        Group 1     Group 2    Leftover

The Algorithm

1. Count k nodes (do we have enough?)
2. Reverse those k nodes
3. Recursively handle the rest
4. Connect everything

Node reverseKGroup(Node head, int k) {
    // Count k nodes
    Node curr = head;
    int count = 0;
    while (curr != null && count < k) {
        curr = curr.next;
        count++;
    }

    // Not enough? Keep as is
    if (count < k) return head;

    // Reverse k nodes
    Node prev = null;
    curr = head;
    for (int i = 0; i < k; i++) {
        Node next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    // head is now tail of reversed
    // Connect to rest (recursively)
    head.next = reverseKGroup(curr, k);

    return prev; // New head
}

Visual Journey

k=2: [1]→[2]→[3]→[4]→[5]

Round 1: Reverse [1,2]
         [2]→[1] [3]→[4]→[5]

Round 2: Reverse [3,4]
         [2]→[1]→[4]→[3] [5]

Round 3: Only [5] left (< k)
         [2]→[1]→[4]→[3]→[5]

🎓 Summary: Your Linked List Toolkit

💡 Golden Rules

1. When stuck: Draw it out! Boxes and arrows.
2. Edge cases: Empty list? One node? Use dummy!
3. Slow + Fast: Solves cycles AND middle problems
4. Reversal: Always track prev, curr, next
5. Partial reversal: Find the boundaries first

You’ve got this! 🚀

Linked lists are like LEGO chains—once you understand how pieces connect, you can build anything!