🔗 Linked Lists: The Train of Data

The Big Picture

Imagine a train. Each train car holds something precious—passengers, cargo, or treasure. But here’s the magical part: each car knows only about the next car in line. The conductor in the first car can find any car by following the chain, one by one.

That’s a Linked List! Each piece of data (a “node”) points to the next one. Unlike an array (which is like assigned seats in a stadium), a linked list is flexible—you can add or remove cars without rebuilding the whole train.

🚂 Singly Linked List

What Is It?

A Singly Linked List is the simplest train. Each car (node) has:

1. Data – the treasure inside
2. Next pointer – a sign pointing to the next car

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

Building Your First Train

// Create nodes (train cars)
let car1 = new Node(10);
let car2 = new Node(20);
let car3 = new Node(30);

// Connect them
car1.next = car2;
car2.next = car3;
// car3.next stays null (end of train)

Visual:

[10] → [20] → [30] → null

Traversing (Walking Through)

To visit every car, start at the front and follow the next signs:

function printList(head) {
  let current = head;
  while (current !== null) {
    console.log(current.value);
    current = current.next;
  }
}

Why is this cool? You don’t need to know how many cars exist. Just follow until null.

🛡️ Sentinel and Dummy Node Pattern

The Problem

Adding or removing the first car is tricky. The head might change! You need special code for edge cases.

The Solution: A Fake Front Car

Imagine putting an empty car at the very front—a “dummy” or “sentinel.” It holds no treasure, but it never moves. Now the real first car is always dummy.next.

function insertAtHead(dummy, value) {
  let newNode = new Node(value);
  newNode.next = dummy.next;
  dummy.next = newNode;
}

Before: [dummy] → [10] → [20] → null After inserting 5: [dummy] → [5] → [10] → [20] → null

Why Use It?

• No special cases! Head changes? Doesn’t matter—dummy.next is always the real head.
• Cleaner code. One pattern for insert/delete anywhere.

// At the end, return dummy.next as the actual head
return dummy.next;

🐢🐇 Floyd’s Cycle Detection

The Mystery

What if someone connected the last car back to an earlier car? The train becomes a loop! If you try to walk through, you’ll walk forever.

The Trick: Two Runners

Send two people walking:

• Turtle 🐢 walks 1 step at a time
• Rabbit 🐇 runs 2 steps at a time

If there’s a loop, the rabbit will lap the turtle and they’ll meet! If there’s no loop, the rabbit reaches the end first.

function hasCycle(head) {
  let slow = head;
  let fast = head;

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

    if (slow === fast) {
      return true; // They met! Loop exists
    }
  }
  return false; // Rabbit reached the end
}

Finding Where the Loop Starts

Once they meet inside the loop, reset one to the head. Move both at 1 step. Where they meet again is the loop’s entrance.

function findCycleStart(head) {
  let slow = head, fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) break;
  }

  if (!fast || !fast.next) return null;

  slow = head;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next;
  }
  return slow; // The entrance!
}

🎯 Finding the Middle of a Linked List

The Challenge

You don’t know the length. How do you find the middle in one pass?

The Same Two-Runner Trick!

• Turtle moves 1 step
• Rabbit moves 2 steps

When rabbit reaches the end, turtle is at the middle!

function findMiddle(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow; // The middle node!
}

Example:

[1] → [2] → [3] → [4] → [5] → null
       ↑           ↑
      slow        fast (moves twice as fast)

Final: slow at [3] (the middle)

For even-length lists, this gives the second middle.

🔄 Linked List Reversal

The Mission

Turn [1] → [2] → [3] → null into [3] → [2] → [1] → null

The Strategy: Three Pointers

Think of it like a conga line doing an about-face:

• prev – who was behind me (starts as null)
• curr – where I am now
• next – who’s ahead (save it before I turn around!)

function reverseList(head) {
  let prev = null;
  let curr = head;

  while (curr !== null) {
    let next = curr.next; // Save next
    curr.next = prev;     // Turn around!
    prev = curr;          // Step forward
    curr = next;
  }
  return prev; // New head
}

Step by step:

Start: null ← (prev)  [1] → [2] → [3] → null
                       ↑
                     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

Return prev → [3] ← [2] ← [1]

🎭 Reverse Linked List II

The Mission

Reverse only part of the list—from position left to position right.

Example: [1] → [2] → [3] → [4] → [5], reverse from position 2 to 4 Result: [1] → [4] → [3] → [2] → [5]

The Strategy

1. Walk to position left - 1 (the node before the reversal zone)
2. Reverse nodes from left to right
3. Reconnect the reversed section

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

  // Step 1: Find the node before reversal
  let prev = dummy;
  for (let i = 1; i < left; i++) {
    prev = prev.next;
  }

  // Step 2: Reverse the sublist
  let curr = prev.next;
  for (let i = 0; i < right - left; i++) {
    let next = curr.next;
    curr.next = next.next;
    next.next = prev.next;
    prev.next = next;
  }

  return dummy.next;
}

Visual (left=2, right=4):

Before: [1] → [2] → [3] → [4] → [5]
             ↑___________↑
             reverse this

After:  [1] → [4] → [3] → [2] → [5]

Why Dummy Node?

If left = 1, we need to change the head itself. The dummy gives us a consistent “before” position.

🎪 Reverse Nodes in k-Group

The Ultimate Challenge

Reverse the list in groups of k. If there aren’t enough nodes left for a full group, leave them as-is.

Example: [1] → [2] → [3] → [4] → [5], k=2 Result: [2] → [1] → [4] → [3] → [5] (5 stays because it’s alone)

The Strategy

1. Check if we have k nodes ahead
2. If yes, reverse this group
3. Connect to the next group (recursively or iteratively)
4. Repeat

function reverseKGroup(head, k) {
  let dummy = new Node(0);
  dummy.next = head;
  let groupPrev = dummy;

  while (true) {
    // Check if k nodes exist
    let kth = getKth(groupPrev, k);
    if (!kth) break;

    let groupNext = kth.next;

    // Reverse the group
    let prev = kth.next;
    let curr = groupPrev.next;
    while (curr !== groupNext) {
      let next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }

    // Connect
    let tmp = groupPrev.next;
    groupPrev.next = kth;
    groupPrev = tmp;
  }
  return dummy.next;
}

function getKth(curr, k) {
  while (curr && k > 0) {
    curr = curr.next;
    k--;
  }
  return curr;
}

Visual (k=3):

Before: [1] → [2] → [3] → [4] → [5] → [6] → [7]
        ↑_________↑   ↑_________↑    ↑___↑
         group 1       group 2      < k (keep)

After:  [3] → [2] → [1] → [6] → [5] → [4] → [7]

🧠 The Pattern Summary

🌟 You’ve Got This!

Linked Lists seem tricky at first, but they follow simple patterns:

• Pointers are just directions – like signs on a treasure map
• Two-pointer tricks solve many problems elegantly
• Dummy nodes eliminate messy edge cases

Practice these operations until they feel natural. Soon you’ll be reversing trains, detecting loops, and manipulating data like a pro!

graph TD
    A[Master Linked Lists] --> B[Understand Nodes]
    B --> C[Practice Traversal]
    C --> D[Learn Two-Pointer]
    D --> E[Conquer Reversal]
    E --> F[Solve Any Problem!]

Remember: Every expert was once a beginner. Keep building those trains! 🚂