Linked List

Easy-Medium

Time: O(n)Space: O(1) for most, O(n) for recursion/HashMap

0/16

problems solved

What is a Linked List?

A linked list is a linear data structure where elements are stored in nodes, and each node points to the next one. Unlike arrays, linked list elements are not stored in contiguous memory locations.

The Train Analogy: Think of a linked list like a train:

•Each train car (node) contains cargo (data)
•Each car is connected to the next car (pointer)
•You can only move forward car by car
•You can't jump directly to car #5 without passing through cars 1-4

Why Linked Lists Exist:

Array: [1][2][3][4][5] ← Contiguous memory

↑ Insert here? Must shift everything!

Linked: 1 -> 2 -> 3 -> 4 -> 5

↑ Insert here? Just change 2 pointers!

Trade-offs vs Arrays:

Operation	Array	Linked List
Access by index	O(1)	O(n)
Insert at beginning	O(n)	O(1)
Insert at end	O(1)*	O(n) or O(1)**
Insert in middle	O(n)	O(1) if position known
Memory	Contiguous	Scattered

*Amortized for dynamic arrays **O(1) if tail pointer maintained

The ListNode Class

Before solving any linked list problem, you must understand the node structure.

The Building Block:

class ListNode {

int val; // The data

ListNode next; // Pointer to next node

ListNode(int val) {

this.val = val;

this.next = null;

}

Visual Representation:

+-------+------+

| val | next | ---> points to another node (or null)

+-------+------+

↑

data

Building a List Manually:

ListNode head = new ListNode(1);

head.next = new ListNode(2);

head.next.next = new ListNode(3);

// Result: 1 -> 2 -> 3 -> null

Key Insight: head is just a pointer to the first node. The list exists in memory; head is how we access it. If we lose head, we lose the entire list!

Why Linked Lists Matter in Interviews

Linked list problems test fundamental skills that translate to other areas.

What Interviewers Are Really Testing:

•Pointer Manipulation - Can you mentally track multiple references?
•Edge Case Handling - Empty list, single node, head changes
•Space Optimization - O(1) space solutions show mastery
•Algorithm Composition - Combining techniques (find middle + reverse + merge)

Frequency in Interviews:

•FAANG: 15-20% of coding rounds include linked list problems
•Most common: Reverse, Cycle Detection, Merge
•Hardest: Reverse K-Group, Copy with Random Pointer

The Four Core Patterns:

1. Iterative Reversal → Reverse entire list or portions

2. Fast/Slow Pointers → Find middle, detect cycles

3. Dummy Node → Simplify when head might change

4. In-Place Reordering → Combine multiple techniques

Golden Rule: ALWAYS draw diagrams! Even experts draw pictures for linked list problems. Pointer manipulation without visualization leads to bugs.

Traversing a Linked List

Before you can manipulate a list, you must know how to traverse it.

Basic Traversal Pattern:

ListNode curr = head;

while (curr != null) {

// Process curr.val

curr = curr.next;

}

Counting Nodes:

int count = 0;

ListNode curr = head;

while (curr != null) {

count++;

curr = curr.next;

}

Finding a Value:

ListNode curr = head;

while (curr != null) {

if (curr.val == target) {

return curr; // Found!

}

curr = curr.next;

}

return null; // Not found

Common Mistake - Using head Directly:

// BAD - loses reference to list!

while (head != null) {

head = head.next;

}

// Now head is null, list is "lost"

// GOOD - preserve head reference

ListNode curr = head;

while (curr != null) {

curr = curr.next;

}

// head still points to start

Iterative Reversal - The Three-Pointer Dance

The most fundamental linked list operation. Master this pattern - it appears everywhere.

The Core Idea: We need three pointers because when we reverse a link, we lose access to the next node. So we must save it first.

The Algorithm:

Step 1: Save next → Don't lose the rest of the list

Step 2: Reverse link → Point current backward

Step 3: Move prev → Advance prev pointer

Step 4: Move curr → Advance to saved next

Visual Trace (MUST UNDERSTAND):

Initial: null 1 -> 2 -> 3 -> null

↑ ↑

prev curr

Iteration 1:

next = 2

1.next = null (reverse link)

prev = 1, curr = 2

null <- 1 2 -> 3 -> null

↑ ↑

prev curr

Iteration 2:

next = 3

2.next = 1 (reverse link)

prev = 2, curr = 3

null <- 1 <- 2 3 -> null

↑ ↑

prev curr

Iteration 3:

next = null

3.next = 2 (reverse link)

prev = 3, curr = null

null <- 1 <- 2 <- 3

↑

prev (new head!)

Code

Java

▶ Interactive Linked List Reversal

Reverse Linked List

Three-pointer technique: prev, curr, next

Speed:

Linked List:

null

curr

→

null

curr

null

The Four Steps (repeated):

1. next = curr.next

2. curr.next = prev

3. prev = curr

4. curr = next

Click Play to reverse the linked list

Key Insight: Use three pointers: prev (already reversed), curr (processing), next (saved reference). Repeat: save next, reverse link, move prev, move curr.

Reverse a Portion of the List

A harder variant: reverse only nodes from position m to n.

Example: Reverse positions 2 to 4

Input: 1 -> 2 -> 3 -> 4 -> 5

[ reverse ]

Output: 1 -> 4 -> 3 -> 2 -> 5

Key Insight: We need to track:

•The node BEFORE the reversed section (to reconnect)
•The FIRST node of reversed section (becomes last)
•Standard reversal within the section

Strategy:

•Move to position m-1 (the node before reversal starts)
•Reverse n-m+1 nodes
•Reconnect: before.next = new_start, old_start.next = after

Code

Java

▶ Interactive Linked List Reversal

Reverse Linked List

Three-pointer technique: prev, curr, next

Speed:

Linked List:

null

curr

→

null

curr

null

The Four Steps (repeated):

1. next = curr.next

2. curr.next = prev

3. prev = curr

4. curr = next

Click Play to reverse the linked list

Key Insight: Use three pointers: prev (already reversed), curr (processing), next (saved reference). Repeat: save next, reverse link, move prev, move curr.

Fast/Slow Pointers - Floyd's Algorithm

Two pointers moving at different speeds reveal hidden information about the list.

The Tortoise and Hare:

•Slow pointer moves 1 step at a time
•Fast pointer moves 2 steps at a time

Why This Works:

Finding Middle: When fast reaches the end, slow has traveled half the distance.

1 -> 2 -> 3 -> 4 -> 5 -> null

^s ^f

1 -> 2 -> 3 -> 4 -> 5 -> null

^s ^f

1 -> 2 -> 3 -> 4 -> 5 -> null

^s ^f (at null)

Slow is at middle (node 3)!

Detecting Cycles: If there's a cycle, fast will eventually lap slow (like runners on a track).

1 -> 2 -> 3 -> 4

↑ ↓

6 <- 5

Fast will keep going in circles until it catches slow.

No cycle? Fast reaches null.

Loop Condition Matters:

// For middle (odd/even handling):

while (fast != null && fast.next != null)

// For cycle detection:

while (fast != null && fast.next != null)

Code

Java

▶ Interactive Cycle Detection

Cycle Detection (Floyd's Algorithm)

Fast/Slow pointers: if they meet, there's a cycle

Speed:

List: 1 → 2 → 3 → 4 → 5 → (back to 3)

Cycle starts at node 3

Slow Pointer

Moves 1 step

Fast Pointer

Moves 2 steps

Step: 0

Click Play to detect cycle using Floyd's algorithm

Key Insight:If there's a cycle, fast will lap slow. After meeting, reset slow to head - they'll meet at cycle start.

Finding Cycle Start - The Mathematical Magic

Finding WHERE a cycle starts is one of the most elegant algorithms in CS.

The Problem:

1 -> 2 -> 3 -> 4 -> 5

↑ ↓

7 <- 6

Cycle starts at node 4. How do we find it?

The Algorithm:

•Detect cycle using fast/slow (they meet somewhere in cycle)
•Move ONE pointer back to head
•Move BOTH pointers one step at a time
•They meet at cycle start!

Why Does This Work? (Simplified)

Let:

- F = distance from head to cycle start

- C = cycle length

- X = distance from cycle start to meeting point

When they meet:

- Slow traveled: F + X

- Fast traveled: F + X + nC (went around cycle n times)

- Fast travels 2x slow: 2(F + X) = F + X + nC

- Therefore: F + X = nC

- Therefore: F = nC - X = (n-1)C + (C - X)

C - X is the distance from meeting point back to cycle start.

So traveling F from head = traveling to cycle start!

Code

Java

▶ Interactive Cycle Detection

Cycle Detection (Floyd's Algorithm)

Fast/Slow pointers: if they meet, there's a cycle

Speed:

List: 1 → 2 → 3 → 4 → 5 → (back to 3)

Cycle starts at node 3

Slow Pointer

Moves 1 step

Fast Pointer

Moves 2 steps

Step: 0

Click Play to detect cycle using Floyd's algorithm

Key Insight:If there's a cycle, fast will lap slow. After meeting, reset slow to head - they'll meet at cycle start.

The Dummy Node Pattern

When the head of the list might change, use a dummy node to avoid special cases.

The Problem:

// Without dummy - messy edge cases!

public ListNode removeElements(ListNode head, int val) {

// Handle head removal - SPECIAL CASE

while (head != null && head.val == val) {

head = head.next;

}

// Handle rest - different logic

ListNode curr = head;

while (curr != null && curr.next != null) {

if (curr.next.val == val) {

curr.next = curr.next.next;

} else {

curr = curr.next;

}

return head;

}

The Solution - Dummy Node:

// With dummy - uniform logic!

public ListNode removeElements(ListNode head, int val) {

ListNode dummy = new ListNode(0);

dummy.next = head;

ListNode curr = dummy; // Start from dummy

while (curr.next != null) {

if (curr.next.val == val) {

curr.next = curr.next.next; // Same logic for all!

} else {

curr = curr.next;

}

return dummy.next; // Real head

}

When to Use Dummy Node:

•Removing nodes (head might be removed)
•Merging lists (result head unknown until comparison)
•Inserting at various positions
•Any operation where head might change

10.

Merge Two Sorted Lists

A classic problem that combines traversal with the dummy node pattern.

The Idea: Compare heads of both lists, take the smaller one, advance that list.

Visual Trace:

L1: 1 -> 3 -> 5

L2: 2 -> 4 -> 6

Compare 1 vs 2: take 1 Result: 1

Compare 3 vs 2: take 2 Result: 1 -> 2

Compare 3 vs 4: take 3 Result: 1 -> 2 -> 3

Compare 5 vs 4: take 4 Result: 1 -> 2 -> 3 -> 4

Compare 5 vs 6: take 5 Result: 1 -> 2 -> 3 -> 4 -> 5

L1 empty, append L2 Result: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Key Points:

•Use dummy node (don't know which list has smaller head)
•Use tail pointer to build result
•When one list exhausts, append the other entirely

Code

Java

11.

Remove Nth Node From End

A clever application of the two-pointer technique with a gap.

The Problem: Remove the nth node from the END of the list in one pass.

Naive Approach: Count length, traverse to (length - n)th node. Two passes.

One-Pass Solution: Use two pointers with n-node gap!

Remove 2nd from end: 1 -> 2 -> 3 -> 4 -> 5

Create n+1 gap (so slow lands BEFORE target):

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null

^slow ^fast (n+1 = 3 steps ahead)

Move both until fast hits null:

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null

^slow ^fast

Now slow.next is the target! Remove it:

slow.next = slow.next.next

Why n+1 Gap? We need slow to point to the node BEFORE the target so we can remove target.

Code

Java

12.

Reorder List - Combining All Techniques

This problem beautifully combines three techniques into one elegant solution.

Problem: Reorder L0 → L1 → ... → Ln to L0 → Ln → L1 → Ln-1 → ...

Example:

Input: 1 -> 2 -> 3 -> 4 -> 5

Output: 1 -> 5 -> 2 -> 4 -> 3

The Strategy (3 Steps):

Step 1: Find Middle (Fast/Slow)

1 -> 2 -> 3 -> 4 -> 5

^middle

First half: 1 -> 2 -> 3

Second half: 4 -> 5

Step 2: Reverse Second Half

First half: 1 -> 2 -> 3

Second half: 5 -> 4 (reversed)

Step 3: Merge Alternating

Take from first: 1

Take from second: 5

Take from first: 2

Take from second: 4

Take from first: 3

Result: 1 -> 5 -> 2 -> 4 -> 3

Code

Java

▶ Interactive Reorder List

Reorder List

Three steps: Find middle → Reverse second half → Merge alternating

Speed:

1. Finding Middle

2. Reversing

3. Merging

Original List (finding middle):

S+F

→

Click Play to reorder the list

Key Insight: Combine three techniques: Fast/slow finds middle, then reverse second half, then interleave both halves. Same pattern works for Palindrome check.

13.

Palindrome Linked List

Check if a linked list is a palindrome using O(1) space.

The Key Insight: Same strategy as Reorder List!

•Find middle
•Reverse second half
•Compare both halves (instead of merging)

Example:

Input: 1 -> 2 -> 2 -> 1

Step 1 - Find middle:

First half: 1 -> 2

Second half: 2 -> 1

Step 2 - Reverse second half:

First half: 1 -> 2

Second half: 1 -> 2

Step 3 - Compare:

1 == 1 ✓

2 == 2 ✓

Both exhausted → Palindrome!

Edge Cases:

•Odd length: Middle node doesn't need comparison
•Single node: Always palindrome
•Empty list: Always palindrome

Code

Java

14.

Odd Even Linked List

Group all odd-indexed nodes together followed by even-indexed nodes.

Problem:

Input: 1 -> 2 -> 3 -> 4 -> 5

(odd)(even)(odd)(even)(odd)

Output: 1 -> 3 -> 5 -> 2 -> 4

[ odds ] [ evens ]

Strategy: Build two separate lists, then connect them.

Visual Trace:

Initial:

odd = 1

even = 2

evenHead = 2 (save this!)

Iteration 1:

odd.next = 3 (skip 2)

odd = 3

even.next = 4 (skip 3)

even = 4

Iteration 2:

odd.next = 5 (skip 4)

odd = 5

even.next = null (skip 5)

even = null

Connect:

odd.next = evenHead

Result: 1 -> 3 -> 5 -> 2 -> 4

Code

Java

15.

Reverse Nodes in K-Group

The hardest linked list problem - combines all techniques. Reverse every k nodes.

Example:

Input: 1 -> 2 -> 3 -> 4 -> 5, k = 2

Output: 2 -> 1 -> 4 -> 3 -> 5

[grp1] [grp2] [<k, keep]

Input: 1 -> 2 -> 3 -> 4 -> 5, k = 3

Output: 3 -> 2 -> 1 -> 4 -> 5

[ group 1 ] [<k, keep]

Strategy for Each Group:

•Check if k nodes exist (if not, stop)
•Reverse the k nodes
•Connect with previous group
•Move to next group

Tracking Pointers:

•groupPrev: Last node of previous group (needed for connection)
•kth: The kth node (will be new first after reversal)
•groupNext: First node after current group

Code

Java

▶ Interactive Linked List Reversal

Reverse Linked List

Three-pointer technique: prev, curr, next

Speed:

Linked List:

null

curr

→

null

curr

null

The Four Steps (repeated):

1. next = curr.next

2. curr.next = prev

3. prev = curr

4. curr = next

Click Play to reverse the linked list

Key Insight: Use three pointers: prev (already reversed), curr (processing), next (saved reference). Repeat: save next, reverse link, move prev, move curr.

16.

Copy List with Random Pointer

Deep copy a list where each node has a random pointer to any node (or null).

The Challenge: Random pointers might point to nodes we haven't created yet!

Solution 1: HashMap (O(n) space) Map original nodes to their copies.

Solution 2: Interweaving (O(1) space) - The Clever Trick

Step 1: Interweave copies

A -> A' -> B -> B' -> C -> C'

Step 2: Set random pointers

If A.random = C, then A'.random = C' = C.next

Step 3: Separate lists

A -> B -> C (original)

A' -> B' -> C' (copy)

Code

Java

17.

Intersection of Two Linked Lists

Find the node where two linked lists intersect (share the same tail).

Visual:

A: a1 -> a2 ↘

c1 -> c2 -> c3

B: b1 -> b2 -> b3 ↗

Intersection at c1

The Elegant Solution: Traverse both lists. When one reaches the end, restart at the OTHER list's head.

Why This Works:

Length of A-only part = a

Length of B-only part = b

Length of shared part = c

Pointer from A travels: a + c + b

Pointer from B travels: b + c + a

They're equal! So they meet at intersection.

Edge Case: If no intersection, both become null together.

Code

Java

18.

Common Edge Cases

Master these edge cases to avoid interview pitfalls.

1. Empty List (head = null)

if (head == null) return ...;

2. Single Node

if (head.next == null) return head; // Already reversed!

3. Two Nodes (Minimum for many operations)

if (head == null || head.next == null) return ...;

4. Even vs Odd Length

Odd: 1 -> 2 -> 3 Middle = 2

Even: 1 -> 2 -> 3 -> 4 Middle = 2 or 3 (depends on problem)

5. Head Changes (Use Dummy Node!)

ListNode dummy = new ListNode(0);

dummy.next = head;

// ... operations ...

return dummy.next; // Might not be original head!

6. Null Pointer Access

// DANGEROUS:

while (curr.next != null) // What if curr is null?

// SAFE:

while (curr != null && curr.next != null)

7. Losing References

// BAD:

curr.next = prev;

curr = curr.next; // curr.next is now prev, not the saved next!

// GOOD:

ListNode next = curr.next; // Save first!

curr.next = prev;

curr = next;

19.

Pattern Recognition Guide

Quick reference for choosing the right technique:

Problem Type	Technique	Key Signal Words
Reverse list	Three pointers	"reverse", "backwards"
Find middle	Fast/slow	"middle", "split", "half"
Cycle detection	Fast/slow	"cycle", "loop", "infinite"
Nth from end	Two pointers with gap	"from end", "kth last"
Merge sorted	Dummy node + comparison	"merge", "combine sorted"
Reorder/Palindrome	Middle + Reverse + Merge	"reorder", "palindrome"
Remove nodes	Dummy node	"remove", "delete", "filter"
Reverse in groups	Count k + Reverse	"k-group", "pairs", "every k"
Intersection	Switch heads technique	"intersect", "common", "share"
Deep copy	HashMap or interweave	"copy", "clone", "random pointer"

Decision Tree:

Is head might change?

YES → Use dummy node

NO → Direct manipulation

Need to find position?

From start → Count

From end → Two pointers with gap

Middle → Fast/slow

Need cycle info?

Just detect → Fast/slow, check if meet

Find start → After detection, reset one to head

Need to reverse?

Full → Three pointer dance

Partial → Track boundaries + three pointer

In groups → Count k + reverse + reconnect

20.

Template Summary

Copy-paste ready templates for common operations.

Template 1: Reverse Entire List

ListNode prev = null, curr = head;

while (curr != null) {

ListNode next = curr.next;

curr.next = prev;

prev = curr;

curr = next;

}

return prev;

Template 2: Find Middle

ListNode slow = head, fast = head;

while (fast != null && fast.next != null) {

slow = slow.next;

fast = fast.next.next;

}

return slow;

Template 3: Detect Cycle Start

ListNode slow = head, fast = head;

while (fast != null && fast.next != null) {

slow = slow.next;

fast = fast.next.next;

if (slow == fast) {

slow = head;

while (slow != fast) {

slow = slow.next;

fast = fast.next;

}

return slow;

}

return null;

Template 4: Merge Two Sorted Lists

ListNode dummy = new ListNode(0);

ListNode tail = dummy;

while (l1 != null && l2 != null) {

if (l1.val <= l2.val) {

tail.next = l1; l1 = l1.next;

} else {

tail.next = l2; l2 = l2.next;

}

tail = tail.next;

}

tail.next = (l1 != null) ? l1 : l2;

return dummy.next;

Template 5: Remove Nth From End

ListNode dummy = new ListNode(0);

dummy.next = head;

ListNode fast = dummy, slow = dummy;

for (int i = 0; i <= n; i++) fast = fast.next;

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

slow.next = slow.next.next;

return dummy.next;

Test Your Knowledge

Take a quick 15question quiz to test what you've learned.