Linked List Patterns

Master this topic with zero to advance depth.

Linked List Fundamentals & Patterns

A Linked List is a linear data structure where elements are not stored in contiguous memory locations. Instead, each node contains a data field and a reference (pointer) to the next node.

1. Types of Linked Lists

Type	Description	Pointers
Singly	Forward traversal only.	`next`
Doubly	Forward and backward traversal.	`next`, `prev`
Circular	Last node points back to head.	`next` (tail -> head)

2. Core Techniques

Dummy Node: A sentinel node placed at the start to avoid edge cases (e.g., deleting head).
Fast & Slow Pointers: Used for cycle detection, finding middle, and k-th node from end.
Two Pointers: Used for merging, intersections, and partitioning.
In-place Reversal: Changing next pointers without using extra memory.

3. Comparison with Arrays

Feature	Linked List	Array
Access	$O(N)$ (Sequential)	$O(1)$ (Random)
Insert/Delete	$O(1)$ (if at known node)	$O(N)$ (Shift required)
Memory	Dynamic (Extra for pointers)	Static/Dynamic (Contiguous)

4. Visualizing Reverse

Initial: [1] -> [2] -> [3] -> null
1. Point [1].next to null
2. Point [2].next to [1]
3. Point [3].next to [2]
Result:  [3] -> [2] -> [1] -> null

Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

List: 3 -> 2 -> 0 -> -4 -> 2... (Cycle)

1. Slow=3, Fast=2
2. Slow=2, Fast=-4
3. Slow=0, Fast=0 (MEET!)
Result: true

Easy

Examples

Input: head = [3,2,0,-4], pos = 1
Output: true
There is a cycle where tail connects to the second node.

Approach 1

Level I: HashSet / Visited Set

Intuition

The simplest way to detect a cycle is to keep track of all nodes seen. If we encounter a node that's already in our 'visited' set, it means there's a cycle.

Visual Trace

List: 3 -> 2 -> 0 -> -4 (points back to 2)

Iter 1: node=3, Set={3}
Iter 2: node=2, Set={3, 2}
Iter 3: node=0, Set={3, 2, 0}
Iter 4: node=-4, Set={3, 2, 0, -4}
Iter 5: node=2, Found in Set! Cycle detected.

Initialize an empty HashSet of node references.
Traverse the list. For each node, check if it exists in the set.
If yes, return true. Otherwise, add the node to the set and move to next node.

⏱ O(N)💾 O(N)

Detailed Dry Run

Input: 3 -> 2 -> 0 -> -4 -> 2 (cycle)

Seen: {3}
Seen: {3, 2}
Seen: {3, 2, 0}
Seen: {3, 2, 0, -4}
Next is 2. 2 is in Seen. Cycle detected!

java

public boolean hasCycle(ListNode head) {
    Set<ListNode> seen = new HashSet<>();
    while (head != null) {
        if (seen.contains(head)) return true;
        seen.add(head);
        head = head.next;
    }
    return false;
}

⚠️ Common Pitfalls & Tips

O(N) space is often not allowed if O(1) is possible.

Approach 2

Level II: Node Marking

Intuition

If we can modify the list, we can point all seen nodes toward a sentinel 'Visited' node. If a node's next already points to this sentinel, we've closed the circle.

Visual Trace

Nodes: [A] -> [B] -> [C] -> [B(cycle)]

At [A]: Save next [B], set [A].next = Sentinel. Move to [B].
At [B]: Save next [C], set [B].next = Sentinel. Move to [C].
At [C]: Save next [B], set [C].next = Sentinel. Move to [B].
At [B]: [B].next is already Sentinel! return true.

⏱ O(N)💾 O(1)

Detailed Dry Run

1 -> 2 -> 1. Point 1.next to dummy. Point 2.next to dummy. 2.next is already dummy? No, 1.next was dummy. When we go from 2 to 1, 1.next is already dummy.

java

public boolean hasCycle(ListNode head) {
    ListNode dummy = new ListNode(0);
    while (head != null) {
        if (head.next == dummy) return true;
        ListNode next = head.next;
        head.next = dummy;
        head = next;
    }
    return false;
}

⚠️ Common Pitfalls & Tips

This destroys the original list.

Approach 3

Level III: Floyd's Cycle Finding (Tortoise and Hare)

Intuition

Use two pointers, slow and fast. slow moves one step, fast moves two. If there's a cycle, the fast pointer will eventually 'lap' the slow pointer.

Visual Trace

List: 1 -> 2 -> 3 -> 4 -> 5 -> (back to 2)

Start: S=1, F=1
Step 1: S=2, F=3
Step 2: S=3, F=5
Step 3: S=4, F=3 (F wrapped around cycle)
Step 4: S=5, F=5 (MEET!)

⏱ O(N)💾 O(1)

Detailed Dry Run

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

Initial: slow=1, fast=2.
Step 1: slow = slow.next (2), fast = fast.next.next (2).
Match! Return true.

java

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

⚠️ Common Pitfalls & Tips

Check both fast and fast.next for null to avoid errors.

Remove Nth Node From End of List

Given the head of a linked list, remove the n^{th} node from the end of the list and return its head.

Visual Representation

List: 1 -> 2 -> 3 -> 4 -> 5, n = 2

Step 1: Move Fast pointer n=2 steps ahead.
        Dummy -> 1 -> 2 -> 3 -> 4 -> 5
          S           F

Step 2: Move both S and F until F reaches the end.
        Dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                           S              F

Step 3: S.next = S.next.next (Removes 4)
        1 -> 2 -> 3 -> 5

Medium

Examples

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
The second node from the end is 4. Removing it results in [1,2,3,5].

Approach 1

Level I: Two Pass (Length Calculation)

Intuition

To remove the n^{th} node from the end, we calculate the total length L of the list. The node to remove is at index (L - n) from the start (0-indexed if using a dummy node).

⏱ O(L)💾 O(1)

Detailed Dry Run

Input: 1->2->3->4->5, n=2. Length = 5. Target to skip: 5 - 2 = 3 steps from dummy.

Steps	Curr	Action
0	Dummy	Move
1	1	Move
2	2	Move
3	3	Stop. `curr` is now at node 3. `curr.next` (node 4) is the one to remove.
		`curr.next = curr.next.next` (node 3 points to node 5)

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int length = 0;
        ListNode first = head;
        while (first != null) {
            length++;
            first = first.next;
        }
        length -= n;
        first = dummy;
        while (length > 0) {
            length--;
            first = first.next;
        }
        first.next = first.next.next;
        return dummy.next;
    }
}

⚠️ Common Pitfalls & Tips

You must handle the case where the head itself is removed. Using a dummy node simplifies this.

Approach 2

Level II: Better (Recursion)

Intuition

We can solve this problem recursively by traversing to the end of the list and then backtracking. During backtracking, we keep track of the node count from the end. When it reaches n, we remove the next node.

Recursively call the function for head.next.
On return, increment a counter.
If counter equals n, the current node's next should be skipped.

⏱ O(L)💾 O(L) (recursion stack)

Detailed Dry Run

Input: 1->2->3, n=1

Push 1, 2, 3 to stack.
Pop 3, count=1. count == n, so return to 2 acknowledging 3 should be removed? (Actually implementation differs slightly).

java

class Solution {
    int count = 0;
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return null;
        head.next = removeNthFromEnd(head.next, n);
        count++;
        if (count == n) return head.next;
        return head;
    }
}

⚠️ Common Pitfalls & Tips

O(L) space due to recursion might be an issue for very long lists.

Approach 3

Level III: Optimal (One Pass - Two Pointers)

Intuition

Use two pointers, fast and slow. Move fast n steps ahead. Then move both until fast reaches the end. slow will now be just before the node to be removed.

Initialize fast and slow pointers at a dummy node.
Move the fast pointer n+1 steps forward.
Move both pointers together until the fast pointer reaches the end (null).
At this point, slow.next is the node to be removed. Update slow.next = slow.next.next.

⏱ O(L)💾 O(1)

Detailed Dry Run

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

Start fast, slow at dummy.
Move fast 3 steps: fast points at 3.
Move both: fast at 4, slow at 1; fast at 5, slow at 2; fast at null, slow at 3.
slow.next (node 4) is removed.

java

public ListNode removeNthFromEnd(ListNode head, int n) {
    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;
}

⚠️ Common Pitfalls & Tips

The gap between fast and slow must be exactly n+1 to land 'slow' on the node before the target.

Visual Representation

List: 1 -> 2 -> 3 -> 4 -> 5, n = 2
[D] -> [1] -> [2] -> [3] -> [4] -> [5] -> null
 S,F

1. Move Fast 3 steps (n+1):
[D] -> [1] -> [2] -> [3] -> [4] -> [5]
 S                    F

2. Move both until F is null:
[D] -> [1] -> [2] -> [3] -> [4] -> [5] -> null
                      S                    F

3. S.next = S.next.next (skip 4):
[3] -> [5]

Partition List

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions.

Visual Representation

List: 1 -> 4 -> 3 -> 2 -> 5 -> 2, x = 3

Step 1: Create two lists: Small and Large.
Step 2: Traverse and assign:
        Small: 1 -> 2 -> 2
        Large: 4 -> 3 -> 5

Step 3: Connect Small.next to Large.next.
Result: 1 -> 2 -> 2 -> 4 -> 3 -> 5

Medium

Examples

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Nodes less than 3 are 1, 2, 2. Nodes >= 3 are 4, 3, 5. Order is preserved.

Approach 1

Level I: Brute Force (Extra Space)

Intuition

Iterate through the list twice (or once with two collections). In the first pass, collect all nodes smaller than x. In the second pass, collect all nodes greater than or equal to x. Finally, rebuild the list.

Visual Trace

List: 1 -> 4 -> 3 -> 2, x=3
Pass 1 (<3): [1, 2]
Pass 2 (>=3): [4, 3]
Combined: [1, 2, 4, 3]
New List: 1 -> 2 -> 4 -> 3

Iterate and store values in two separate lists (or an array). Traverse the stored values to create a new linked list.

⏱ O(N)💾 O(N)

Detailed Dry Run

Input: [1, 4, 3, 2], x=3 Lists: Small=[1, 2], Large=[4, 3]. Rebuild: 1->2->4->3.

java

public ListNode partition(ListNode head, int x) {
    List<Integer> small = new ArrayList<>(), large = new ArrayList<>();
    ListNode curr = head;
    while (curr != null) {
        if (curr.val < x) small.add(curr.val);
        else large.add(curr.val);
        curr = curr.next;
    }
    ListNode dummy = new ListNode(0), res = dummy;
    for (int v : small) { res.next = new ListNode(v); res = res.next; }
    for (int v : large) { res.next = new ListNode(v); res = res.next; }
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

O(N) space is not ideal. Rebuilding the list creates new node objects.

Approach 2

Level II: In-place Node Movement

Intuition

If we don't care about relative order, we could swap values. Since we must preserve it, this approach involves detaching nodes >= x and appending them to a secondary 'large' list, while keeping < x nodes in the 'small' list.

Visual Trace

List: 1 -> 4 -> 3 -> 2, x=3
Small Head: [DummyS]
Large Head: [DummyL]

Node 1: <3, DummyS -> 1
Node 4: >=3, DummyL -> 4
Node 3: >=3, DummyL -> 4 -> 3
Node 2: <3, DummyS -> 1 -> 2
Connect: DummyS -> 1 -> 2 -> 4 -> 3

Iterate through the list. If a node is >= x, move it to a temporary 'large' list. If < x, keep it in the 'small' list. This is similar to Level III but implemented strictly with node movement.

⏱ O(N)💾 O(1)

Detailed Dry Run

Identical to Level III intuition but focused on pointer manipulation without separate head nodes.

java

public ListNode partition(ListNode head, int x) {
    ListNode dummy = new ListNode(0, head), prev = dummy, curr = head;
    ListNode tailHead = new ListNode(0), tail = tailHead;
    while (curr != null) {
        if (curr.val >= x) {
            prev.next = curr.next;
            tail.next = curr;
            tail = tail.next;
        } else {
            prev = curr;
        }
        curr = curr.next;
    }
    tail.next = null;
    prev.next = tailHead.next;
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

Strict pointer management is required to avoid cycles or losing nodes.

Approach 3

Level III: Optimal (Two Pointer - Separate Lists)

Intuition

The simplest way to maintain relative order is to create two separate lists: one for nodes smaller than x and another for nodes greater than or equal to x. Finally, link the end of the first list to the head of the second list.

⏱ O(N)💾 O(1) (new nodes are just pointers to existing ones)

Detailed Dry Run

Input: 1->4->3->2, x=3

1 < 3: Small: 1
4 >= 3: Large: 4
3 >= 3: Large: 4->3
2 < 3: Small: 1->2
End: Connect 1->2 to 4->3 -> 1->2->4->3

java

public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode beforeHead = new ListNode(0);
        ListNode afterHead = new ListNode(0);
        ListNode before = beforeHead, after = afterHead;
        while (head != null) {
            if (head.val < x) {
                before.next = head;
                before = before.next;
            } else {
                after.next = head;
                after = after.next;
            }
            head = head.next;
        }
        after.next = null;
        before.next = afterHead.next;
        return beforeHead.next;
    }
}

⚠️ Common Pitfalls & Tips

Remember to set after.next = null to avoid cycles in the list.

Merge K Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Visual Representation

lists = [
  1->4->5,
  1->3->4,
  2->6
]

Min-Heap State:
1. Insert heads: [1, 1, 2]
2. Extract 1, add next(4): Heap = [1, 2, 4]
3. Extract 1, add next(3): Heap = [2, 3, 4]
4. Extract 2, add next(6): Heap = [3, 4, 6]...

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

Hard

Examples

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Input: lists = []
Output: []

Approach 1

Level I: Brute Force (Array + Sort)

Intuition

The simplest approach is to ignore the linked list structure initially. We can traverse all the linked lists, collect all the values into an array, sort the array, and then build a new linked list from the sorted array.

⏱ O(N log N) where N is the total number of nodes💾 O(N) to store all values in the array and the new linked list

Detailed Dry Run

lists = [[1,4,5],[1,3,4],[2,6]]

Collect: [1,4,5,1,3,4,2,6]
Sort: [1,1,2,3,4,4,5,6]
Build new list: 1->1->2->3->4->4->5->6

java

import java.util.*;

public class Main {
    public static ListNode mergeKLists(ListNode[] lists) {
        List<Integer> values = new ArrayList<>();
        for (ListNode list : lists) {
            while (list != null) {
                values.add(list.val);
                list = list.next;
            }
        }
        Collections.sort(values);
        
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (int val : values) {
            current.next = new ListNode(val);
            current = current.next;
        }
        return dummy.next;
    }
}

⚠️ Common Pitfalls & Tips

O(N log N) time and O(N) space. Not optimal for large lists.

Visual Trace

Lists: [1->4, 1->3]
Array: [1, 4, 1, 3]
Sorted: [1, 1, 3, 4]
Linked: 1 -> 1 -> 3 -> 4

Approach 2

Level II: Divide and Conquer

Intuition

Merge lists in pairs, decreasing the number of lists by half in each step. This is more efficient than merging one by one and avoids the overhead of a Min-Heap if k is small.

Visual Trace

[L1, L2, L3, L4]
  \ /    \ /
 [L12]  [L34]
   \    /
    [Final]

⏱ O(N log K)💾 O(log K) recursion

Detailed Dry Run

Lists = [L1, L2, L3, L4]. 1. Merge(L1, L2)=L12, Merge(L3, L4)=L34. 2. Merge(L12, L34) = Result.

java

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    return merge(lists, 0, lists.length - 1);
}
private ListNode merge(ListNode[] lists, int left, int right) {
    if (left == right) return lists[left];
    int mid = left + (right - left) / 2;
    ListNode l1 = merge(lists, left, mid);
    ListNode l2 = merge(lists, mid + 1, right);
    return mergeTwoLists(l1, l2);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), 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;
}

⚠️ Common Pitfalls & Tips

Deep recursion could cause stack overflow in some environments, though log(k) is usually safe.

Approach 3

Level III: Min-Heap (Optimal)

Intuition

Use a Min-Heap (Priority Queue) to always extract the smallest current node among the heads of all k lists.

⏱ O(N log K) where N is total nodes and K is the number of lists💾 O(K) for the Min-Heap

Detailed Dry Run

lists = [[1,4,5], [1,3,4], [2,6]]

Heap: [(1: from L1), (1: from L2), (2: from L3)]
Pop 1 (L1). Res: [1]. Push 4 (L1). Heap: [1, 2, 4]
Pop 1 (L2). Res: [1,1]. Push 3 (L2). Heap: [2, 3, 4]...

java

public class Main {
    public static ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode node : lists) {
            if (node != null) minHeap.add(node);
        }
        ListNode dummy = new ListNode(0), tail = dummy;
        while (!minHeap.isEmpty()) {
            ListNode smallest = minHeap.poll();
            tail.next = smallest;
            tail = tail.next;
            if (smallest.next != null) minHeap.add(smallest.next);
        }
        return dummy.next;
    }
}

⚠️ Common Pitfalls & Tips

In Python, using a tie-breaker like i or a wrapper is necessary for heapq when values are equal.

Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

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

1. Group [1,2,3] -> Reverse -> 3 -> 2 -> 1
2. Group [4,5] (Size 2 < 3) -> Keep 4 -> 5
Result: 3 -> 2 -> 1 -> 4 -> 5

Hard

Examples

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
The list is reversed in groups of size 2.

Approach 1

Level I: Recursive Approach

Intuition

We can solve the problem recursively by reversing the first k nodes and then calling the function recursively for the rest of the list.

⏱ O(N)💾 O(N/k) recursion stack

Detailed Dry Run

List: 1->2->3->4->5, k=2.

First 2 nodes: 1->2. Reverse: 2->1.
Recursive call on 3->4->5.
Link 1 to the result of recursive call.

java

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode curr = head;
    int count = 0;
    while (curr != null && count != k) {
        curr = curr.next;
        count++;
    }
    if (count == k) {
        curr = reverseKGroup(curr, k);
        while (count-- > 0) {
            ListNode tmp = head.next;
            head.next = curr;
            curr = head;
            head = tmp;
        }
        head = curr;
    }
    return head;
}

⚠️ Common Pitfalls & Tips

O(N/k) recursion stack space is used. The last group with < k nodes must be left as is.

Approach 2

Level II: Iterative with Stack

Intuition

Traverse the list and push k nodes onto a stack. If we have k nodes, pop them to reverse. If we reach the end with fewer than k nodes, append them as is.

Visual Trace

List: 1 -> 2 -> 3 -> 4, k=2

Iter 1: Stack=[1, 2]. Pop: 2 -> 1
Iter 2: Stack=[3, 4]. Pop: 4 -> 3
Result: 2 -> 1 -> 4 -> 3

⏱ O(N)💾 O(k)

Detailed Dry Run

List: 1->2->3, k=2. Stack=[1, 2], pop to get 2->1. Append 3.

java

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0), tail = dummy, curr = head;
    while (curr != null) {
        Stack<ListNode> s = new Stack<>();
        ListNode tmp = curr;
        while (tmp != null && s.size() < k) {
            s.push(tmp);
            tmp = tmp.next;
        }
        if (s.size() == k) {
            while (!s.isEmpty()) {
                tail.next = s.pop();
                tail = tail.next;
            }
            tail.next = tmp;
            curr = tmp;
        } else {
            tail.next = curr;
            break;
        }
    }
    return dummy.next;
}

Approach 3

Level III: Optimal (Iterative Constant Space)

Intuition

To achieve O(1) space, we can iterate through the list and reverse the nodes in-place group by group. We use a dummy node to handle the head of the list properly.

⏱ O(N)💾 O(1)

Detailed Dry Run

Dummy -> 1 -> 2 -> 3 -> 4 -> 5, k=2.

Reverse 1, 2: Dummy -> 2 -> 1 -> 3.
Next group 3, 4: Dummy -> 2 -> 1 -> 4 -> 3 -> 5.

java

public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || k == 1) return head;
    ListNode dummy = new ListNode(0); dummy.next = head;
    ListNode curr = dummy, nxt = dummy, prev = dummy;
    int count = 0;
    while (curr.next != null) { curr = curr.next; count++; }
    while (count >= k) {
        curr = prev.next;
        nxt = curr.next;
        for (int i = 1; i < k; i++) {
            curr.next = nxt.next;
            nxt.next = prev.next;
            prev.next = nxt;
            nxt = curr.next;
        }
        prev = curr;
        count -= k;
    }
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

Careful with pointer manipulations. Ensure the count check correctly stops when fewer than k nodes remain.

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Visual Representation

L1: 1 -> 2 -> 4
L2: 1 -> 3 -> 4

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

Easy

Examples

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Approach 1

Level I: Iterative

Intuition

Use a dummy node and a tail pointer. Compare the heads of both lists, attach the smaller node to the tail, and move pointers forward.

Visual Pointer Walk

L1: [1] -> [3]
L2: [2] -> [4]

1. Compare 1 and 2. Attach 1. Tail=[1], L1=[3]
2. Compare 3 and 2. Attach 2. Tail=[2], L2=[4]
3. Compare 3 and 4. Attach 3. Tail=[3], L1=null
4. Attach remaining L2: Tail points to [4].

⏱ O(N + M) where N, M are lengths of the lists💾 O(1)

Detailed Dry Run

L1: 1->2, L2: 1->3. Dummy -> 1 (L1) -> 1 (L2) -> 2 (L1) -> 3 (L2).

java

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    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;
}

⚠️ Common Pitfalls & Tips

Don't forget to attach the remaining nodes at the end.

Approach 2

Level III: Optimized In-place (No Dummy)

Intuition

Merge the lists in-place by always picking the smaller node as the current head and moving pointers. This avoids the use of a dummy node by handling the first node comparison separately.

⏱ O(N + M)💾 O(1)

Detailed Dry Run

L1: 1->3, L2: 2->4.

L1.val (1) < L2.val (2). Result head is 1.
Iterate and link nodes in-place.

java

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    ListNode head = null;
    if (l1.val <= l2.val) { head = l1; l1 = l1.next; } 
    else { head = l2; l2 = l2.next; }
    ListNode curr = head;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
        else { curr.next = l2; l2 = l2.next; }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return head;
}

⚠️ Common Pitfalls & Tips

Must handle the head assignment carefully to avoid null pointer exceptions.

Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Visual Representation

List: 1 -> 2 -> 3 -> null

Step 1: Current=1, Next=2. 1.next points to null.
Step 2: Current=2, Next=3. 2.next points to 1.
Step 3: Current=3, Next=null. 3.next points to 2.

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

Easy

Examples

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Approach 1

Level I: Brute Force (Stack)

Intuition

Push all node values onto a stack. Since a stack is Last-In-First-Out (LIFO), popping them will give the values in reverse order. Then, create a new list with these values.

⏱ O(N)💾 O(N)

Detailed Dry Run

List: 1->2->3.

Push 1, 2, 3 to stack.
Pop 3: New list 3.
Pop 2: 3->2.
Pop 1: 3->2->1.

java

public ListNode reverseList(ListNode head) {
    Stack<Integer> stack = new Stack<>();
    while (head != null) {
        stack.push(head.val);
        head = head.next;
    }
    ListNode dummy = new ListNode(0), curr = dummy;
    while (!stack.isEmpty()) {
        curr.next = new ListNode(stack.pop());
        curr = curr.next;
    }
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

O(N) space makes this less efficient than in-place methods.

Approach 2

Level II: Recursive

Intuition

Base case: if head is null or next node is null, return head. Recursive step: reverse the rest of the list, then point the next node's next back to head.

⏱ O(N)💾 O(N) recursion stack

Detailed Dry Run

1->2->3.

reverseList(2->3).
reverseList(3) returns 3.
Back at 2: 2.next (3).next = 2. 2.next = null. List: 3->2->null.
Back at 1: 1.next (2).next = 1. 1.next = null. List: 3->2->1->null.

java

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

⚠️ Common Pitfalls & Tips

Easy to forget to set head.next = null, causing deep cycles.

Approach 3

Level III: Optimal (Iterative In-place)

Intuition

Use three pointers: prev, curr, and next. Iterate through the list, changing each node's next pointer to point to the prev node.

⏱ O(N)💾 O(1)

Detailed Dry Run

1->2->3. Prev=null, Curr=1.

Next=2. 1.next=null. Prev=1, Curr=2.
Next=3. 2.next=1. Prev=2, Curr=3.
Next=null. 3.next=2. Prev=3, Curr=null. Return Prev (3).

java

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

⚠️ Common Pitfalls & Tips

Make sure to return prev at the end, as curr will be null.

Visual Pointer Reversal

[1] -> [2] -> [3] -> null
p=null, c=1

Iter 1: [1].next=null, p=1, c=2
Iter 2: [2].next=1, p=2, c=3
Iter 3: [3].next=2, p=3, c=null
Return p=3: [3] -> [2] -> [1] -> null

Middle of the Linked List

Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

Visual Representation

List: 1 -> 2 -> 3 -> 4 -> 5
Slow moves 1 step, Fast moves 2 steps.

Start: Slow=1, Fast=1
Step 1: Slow=2, Fast=3
Step 2: Slow=3, Fast=5

Result: 3 is middle node.

Easy

Examples

Input: head = [1,2,3,4,5]
Output: [3,4,5]

Approach 1

Level I: Brute Force (Array)

Intuition

Convert the linked list into an array. Then, return the node at index size / 2.

⏱ O(N)💾 O(N)

Detailed Dry Run

List: 1->2->3. Array: [1, 2, 3]. Middle index 3/2 = 1. Array[1] = 2.

java

public ListNode middleNode(ListNode head) {
    List<ListNode> nodes = new ArrayList<>();
    while (head != null) {
        nodes.add(head);
        head = head.next;
    }
    return nodes.get(nodes.size() / 2);
}

⚠️ Common Pitfalls & Tips

O(N) space is not optimal.

Visual Mapping

List: A -> B -> C -> D
Array: [A, B, C, D]
Size: 4
Middle: size/2 = 2
Result: Array[2] = C

Approach 2

Level II: Two Pass (Length Calculation)

Intuition

First, traverse the list to find the total number of nodes (N). Then, traverse a second time for N/2 steps to reach the middle node.

⏱ O(N)💾 O(1)

Detailed Dry Run

List: 1->2->3->4.

Pass 1: Count = 4.
Target index = 4/2 = 2.
Pass 2: Move to index 2 (node with value 3).

java

public ListNode middleNode(ListNode head) {
    int length = 0;
    ListNode curr = head;
    while (curr != null) { length++; curr = curr.next; }
    curr = head;
    for (int i = 0; i < length / 2; i++) { curr = curr.next; }
    return curr;
}

⚠️ Common Pitfalls & Tips

Ensure the loop runs exactly length/2 times to handle both even and odd lengths correctly.

Approach 3

Level III: Optimal (Two Pointers - Fast & Slow)

Intuition

Use two pointers, slow and fast. Move slow one step at a time and fast two steps at a time. When fast reaches the end, slow will be at the middle.

⏱ O(N)💾 O(1)

Detailed Dry Run

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

S=1, F=1.
S=2, F=3.
S=3, F=5. F.next is null, return S=3.

java

public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

⚠️ Common Pitfalls & Tips

For even length lists, ensure the second middle node is returned (this implementation does that).

Reorder List

You are given the head of a singly linked-list. The list can be represented as: L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form: L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Visual Representation

List: 1 -> 2 -> 3 -> 4
Find middle: 2
Reverse second half: 4 -> 3
Merge lists: 1 -> 4 -> 2 -> 3

Medium

Examples

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Approach 1

Level I: Brute Force (Array/Stack)

Intuition

Store all nodes in an array. Use two pointers (start and end) to reorder the nodes by changing their next pointers.

⏱ O(N)💾 O(N)

Detailed Dry Run

1->2->3->4. Array: [1, 2, 3, 4].

1.next = 4.
4.next = 2.
2.next = 3.
3.next = null.

java

public void reorderList(ListNode head) {
    if (head == null) return;
    List<ListNode> nodes = new ArrayList<>();
    while (head != null) {
        nodes.add(head);
        head = head.next;
    }
    int i = 0, j = nodes.size() - 1;
    while (i < j) {
        nodes.get(i).next = nodes.get(j);
        i++;
        if (i == j) break;
        nodes.get(j).next = nodes.get(i);
        j--;
    }
    nodes.get(i).next = null;
}

⚠️ Common Pitfalls & Tips

O(N) space makes this less efficient than in-place methods.

Visual Trace (Array/Stack)

List: 1 -> 2 -> 3 -> 4
Array: [1, 2, 3, 4]
i=0, j=3: 1.next=4, 4.next=2
i=1, j=2: 2.next=3
i=2, j=2: Break. 3.next=null
Result: 1 -> 4 -> 2 -> 3

Approach 2

Level II: Using a Stack

Intuition

Store all nodes in a stack. Since a stack is LIFO, popping from it gives nodes from the end. Only pop N/2 nodes and interleave them with the first half of the list.

⏱ O(N)💾 O(N)

Detailed Dry Run

1->2->3->4. Stack: [1, 2, 3, 4].

Pop 4, link after 1: 1->4->2.
Pop 3, link after 2: 1->4->2->3. Wait, stop after N/2 swaps.

java

public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    Stack<ListNode> stack = new Stack<>();
    ListNode curr = head;
    while (curr != null) { stack.push(curr); curr = curr.next; }
    int n = stack.size();
    curr = head;
    for (int i = 0; i < n / 2; i++) {
        ListNode next = curr.next;
        ListNode last = stack.pop();
        curr.next = last;
        last.next = next;
        curr = next;
    }
    curr.next = null;
}

⚠️ Common Pitfalls & Tips

Be careful to set the final next pointer to null to prevent cycles.

Approach 3

Level III: Optimal (Middle + Reverse + Merge)

Intuition

Find the middle of the list. Reverse the second half. Merge the two halves one by one.

⏱ O(N)💾 O(1)

Detailed Dry Run

1->2->3->4.

Mid: 2.
Reverse 3->4 to 4->3.
Merge (1->2) and (4->3): 1->4->2->3.

java

public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
    }
    ListNode prev = null, curr = slow.next; slow.next = null;
    while (curr != null) {
        ListNode tmp = curr.next; curr.next = prev; prev = curr; curr = tmp;
    }
    ListNode first = head, second = prev;
    while (second != null) {
        ListNode tmp1 = first.next, tmp2 = second.next;
        first.next = second; second.next = tmp1;
        first = tmp1; second = tmp2;
    }
}

⚠️ Common Pitfalls & Tips

Ensure to cut the list at the middle (slow.next = null) to avoid cycles.

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list.

Visual Representation

Original: [7,null] -> [13,0] -> [11,4] -> [10,2] -> [1,0]
Where [val, random_index]

Approach: Interweaving
1. Interweave: 7 -> 7' -> 13 -> 13' -> ...
2. Assign random: 7'.random = 7.random.next
3. Separate: 7 -> 13 and 7' -> 13'

Medium

Examples

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Approach 1

Level I: Using HashMap

Intuition

Use a hash map to store the mapping between the original node and the new node. First pass: create all clone nodes and map them. Second pass: link next and random pointers using the map.

⏱ O(N)💾 O(N)

Detailed Dry Run

Map: {7: 7', 13: 13', ...}.

7'.next = Map[7.next] -> 13'.
7'.random = Map[7.random] -> null.

java

public Node copyRandomList(Node head) {
    if (head == null) return null;
    Map<Node, Node> map = new HashMap<>();
    Node curr = head;
    while (curr != null) { map.put(curr, new Node(curr.val)); curr = curr.next; }
    curr = head;
    while (curr != null) {
        map.get(curr).next = map.get(curr.next);
        map.get(curr).random = map.get(curr.random);
        curr = curr.next;
    }
    return map.get(head);
}

⚠️ Common Pitfalls & Tips

O(N) space is required for the map. Ensure the Node structure (with val, next, random) is understood.

Visual Mapping

Original: [A] -> [B] -> [C]
Map: {A: A', B: B', C: C'}
Step 2: A'.next = Map[B], A'.random = Map[C]

Approach 2

Level II: Recursive DFS with Map

Intuition

Use recursion to traverse the list. For each node, create a clone if it doesn't exist, and store it in a map. Then recursively copy next and random pointers. This naturally handles cycles and arbitrary pointers.

⏱ O(N)💾 O(N)

Detailed Dry Run

copy(7) -> 7'.

7'.next = copy(13).
7'.random = copy(null). Recursion handles the rest via map memoization.

java

private Map<Node, Node> visited = new HashMap<>();
public Node copyRandomList(Node head) {
    if (head == null) return null;
    if (visited.containsKey(head)) return visited.get(head);
    Node node = new Node(head.val);
    visited.put(head, node);
    node.next = copyRandomList(head.next);
    node.random = copyRandomList(head.random);
    return node;
}

⚠️ Common Pitfalls & Tips

Recursive depth can be an issue for very large lists. Ensure the map is used to prevent infinite recursion on random pointers.

Approach 3

Level III: Optimal (Interweaving Nodes)

Intuition

Instead of a hash map, we can interweave the cloned nodes with the original nodes. Step 1: Create a clone and insert it after each original node. Step 2: Assign random pointers. Step 3: Separate the interweaved lists.

⏱ O(N)💾 O(1)

Detailed Dry Run

7 -> 13 to 7 -> 7' -> 13 -> 13'.

7'.random = 7.random.next.
Original: 7->13, Copy: 7'->13'.

java

public Node copyRandomList(Node head) {
    if (head == null) return null;
    Node curr = head;
    while (curr != null) { Node next = curr.next; curr.next = new Node(curr.val); curr.next.next = next; curr = next; }
    curr = head;
    while (curr != null) { if (curr.random != null) curr.next.random = curr.random.next; curr = curr.next.next; }
    Node dummy = new Node(0), copyTail = dummy, original = head;
    while (original != null) {
        Node copy = original.next;
        original.next = copy.next;
        copyTail.next = copy;
        copyTail = copy;
        original = original.next;
    }
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

Be extremely careful when separating the interweaved list; you must restore the original list as well.

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Visual Representation

(2 -> 4 -> 3) + (5 -> 6 -> 4) = 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Medium

Examples

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]

Approach 1

Level I: Iterative (Elementary Math)

Intuition

Iterate through both lists, adding digits along with a carry. Create a new node for each digit of the sum.

⏱ O(max(N, M)) where N and M are lengths of the lists💾 O(max(N, M)) for the result list

Detailed Dry Run

l1=[2,4], l2=[5,6].

2+5=7, carry=0.
4+6=10, carry=1. Node 0.
Final carry 1. Node 1. Result: 7->0->1.

java

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int x = (l1 != null) ? l1.val : 0;
        int y = (l2 != null) ? l2.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

Be careful with the final carry; don't forget to add a node for it if it's non-zero.

Approach 2

Level II: Recursive

Intuition

Treat the addition of two lists as a recursive operation: add the current nodes and carry, then recurse for the next nodes.

⏱ O(max(N, M))💾 O(max(N, M)) recursion stack

Detailed Dry Run

l1=[2,4], l2=[5,6].

Add(2, 5, 0): val=7, next=Add(4, 6, 0).
Add(4, 6, 0): val=0, next=Add(null, null, 1).
Add(null, null, 1): val=1, next=null. Result: 7->0->1.

java

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    return add(l1, l2, 0);
}
private ListNode add(ListNode l1, ListNode l2, int carry) {
    if (l1 == null && l2 == null && carry == 0) return null;
    int val = carry + (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0);
    ListNode res = new ListNode(val % 10);
    res.next = add(l1 != null ? l1.next : null, l2 != null ? l2.next : null, val / 10);
    return res;
}

⚠️ Common Pitfalls & Tips

Ensure the base case handles the final carry correctly.

Approach 3

Level III: Optimized Iterative (In-place Re-use)

Intuition

To optimize space, we can re-use the nodes of the longer list instead of creating new ones. However, this is only possible if modifying the input is allowed.

Determine which list is longer (or just pick one).
Add values and carry to the existing nodes.
If the list ends while carry > 0, append a new node.

⏱ O(max(N, M))💾 O(1) extra space (excluding result)

Detailed Dry Run

l1=[2,4], l2=[5,6,7]. Re-use l2.

l2[0] = (2+5)%10 = 7. carry=0.
l2[1] = (4+6)%10 = 0. carry=1.
l2[2] = (1+7)%10 = 8. carry=0. Return l2.

java

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    dummy.next = l1;
    ListNode curr = dummy, p1 = l1, p2 = l2;
    int carry = 0;
    while (p1 != null || p2 != null || carry != 0) {
        int sum = carry + (p1 != null ? p1.val : 0) + (p2 != null ? p2.val : 0);
        carry = sum / 10;
        if (p1 != null) {
            p1.val = sum % 10;
            curr = p1; p1 = p1.next;
        } else {
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
        }
        if (p2 != null) p2 = p2.next;
    }
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

Modifying input lists is generally discouraged unless specified, but it's a valid 'memory-constrained' strategy.

Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

Visual Representation

List A: a1 -> a2 
                 \ 
                  c1 -> c2 -> c3
                 / 
List B: b1 -> b2 -> b3

Intersection at c1.

Easy

Examples

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'

Approach 1

Level I: Brute Force (Hashing)

Intuition

Traverse the first list and store all node addresses in a hash set. Then, traverse the second list and check if any node exists in the set.

⏱ O(N + M)💾 O(N) or O(M)

Detailed Dry Run

List A: [A, B, C]. Set: {A, B, C}. List B: [D, E, B, C]. Search D (no), E (no), B (yes!). Intersection at B.

java

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Set<ListNode> set = new HashSet<>();
    while (headA != null) { set.add(headA); headA = headA.next; }
    while (headB != null) {
        if (set.contains(headB)) return headB;
        headB = headB.next;
    }
    return null;
}

⚠️ Common Pitfalls & Tips

O(N) space is not ideal. Note that you must store node pointers/references, not just values.

Approach 2

Level II: Length Difference

Intuition

Calculate lengths of both lists. Move the pointer of the longer list forward by the difference. Then move both pointers together until they meet.

Visual Trace

A: 1 -> 2 -> 3 -> C1 (Len 4)
B: 4 -> C1 (Len 2)
Diff = 2. Advance pointer A by 2 steps.
Pointer A starts at 3, B starts at 4.
Move both: A=C1, B=C1. Match!

⏱ O(N + M)💾 O(1)

Detailed Dry Run

A: [4,1,8,4,5], B: [5,6,1,8,4,5]. LenA=5, LenB=6. Diff=1. Move B forward by 1 (to 6). Both move together: (1,1), (8,8) -> Intersect at 8.

java

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int lenA = getLen(headA), lenB = getLen(headB);
    while (lenA > lenB) { headA = headA.next; lenA--; }
    while (lenB > lenA) { headB = headB.next; lenB--; }
    while (headA != headB) { headA = headA.next; headB = headB.next; }
    return headA;
}
private int getLen(ListNode h) {
    int l = 0; while (h != null) { l++; h = h.next; } return l;
}

Approach 3

Level III: Optimal (Two Pointers)

Intuition

Use two pointers, pA and pB. Traverse both lists. When a pointer reaches the end, redirect it to the head of the other list. They will meet at the intersection point or both become null.

⏱ O(N + M)💾 O(1)

Detailed Dry Run

A: [1,2,c], B: [3,c].

pA=1, pB=3.
pA=2, pB=c.
pA=c, pB=null->pA=1.
pA=null->pB=3, pB=c. They meet after switched paths.

java

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode a = headA, b = headB;
    while (a != b) {
        a = (a == null) ? headB : a.next;
        b = (b == null) ? headA : b.next;
    }
    return a;
}

⚠️ Common Pitfalls & Tips

The pointers will meet even if there is no intersection (both will be null).

Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Visual Representation

List: 1 -> 2 -> 2 -> 1
Find mid: 2 (first 2)
Reverse second half: 1 -> 2
Compare halves: (1,2) == (1,2) -> true

Easy

Examples

Input: head = [1,2,2,1]
Output: true

Approach 1

Level I: Brute Force (Array Copy)

Intuition

Copy the values of the linked list into an array and then check if the array is a palindrome using two pointers.

⏱ O(N)💾 O(N)

Detailed Dry Run

1->2->2->1. Array: [1,2,2,1]. i=0, j=3: 1==1. i=1, j=2: 2==2. Match!

java

public boolean isPalindrome(ListNode head) {
    List<Integer> vals = new ArrayList<>();
    while (head != null) { vals.add(head.val); head = head.next; }
    int i = 0, j = vals.size() - 1;
    while (i < j) { if (!vals.get(i).equals(vals.get(j))) return false; i++; j--; }
    return true;
}

⚠️ Common Pitfalls & Tips

O(N) space is required.

Visual Trace (Array)

List: 1 -> 2 -> 3 -> 2 -> 1
Array: [1, 2, 3, 2, 1]
i=0, j=4: 1==1
i=1, j=3: 2==2
Match!

Approach 2

Level II: Recursive / Stack-based

Intuition

Compare nodes from outside-in. A stack helps us access nodes in reverse order.

Visual Trace (Stack)

Stack: [1, 2, 2, 1]
Compare Pop(1) with Head(1) -> Match

⏱ O(N)💾 O(N)

java

public boolean isPalindrome(ListNode head) {
    Stack<Integer> stack = new Stack<>();
    ListNode curr = head;
    while (curr != null) { stack.push(curr.val); curr = curr.next; }
    curr = head;
    while (curr != null) { if (curr.val != stack.pop()) return false; curr = curr.next; }
    return true;
}

Approach 3

Level III: Optimal (Reverse Second Half)

Intuition

Find the middle of the linked list using fast/slow pointers. Reverse the second half of the list. Compare the two halves. Finally, restore the list (optional).

⏱ O(N)💾 O(1)

Detailed Dry Run

1->2->2->1.

Mid: 2.
Reverse second half: 1->2.
Compare (1->2) and (1->2).

java

public boolean isPalindrome(ListNode head) {
    if (head == null) return true;
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode prev = null, curr = slow;
    while (curr != null) { ListNode tmp = curr.next; curr.next = prev; prev = curr; curr = tmp; }
    ListNode p1 = head, p2 = prev;
    while (p2 != null) { if (p1.val != p2.val) return false; p1 = p1.next; p2 = p2.next; }
    return true;
}

⚠️ Common Pitfalls & Tips

Be careful when the list length is odd; the slow pointer will be exactly at the middle node, and reversing from it works fine.

Remove Duplicates from Sorted List

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Visual Representation

List: 1 -> 1 -> 2 -> 3 -> 3
1. 1 == 1. 1.next points to 2.
2. 2 != 1. Move to 2.
3. 3 == 3. 3.next points to null.

Result: 1 -> 2 -> 3

Easy

Examples

Input: head = [1,1,2,3,3]
Output: [1,2,3]

Approach 1

Level I: Iterative

Intuition

Since the list is sorted, nodes with the same value will be adjacent. Traverse the list, and if a node's value equals its next node's value, skip the next node.

⏱ O(N)💾 O(1)

Detailed Dry Run

1->1->2.

head=1, next=1. Val 1 == 1. 1.next = 1.next.next = 2.
head=1, next=2. Val 1 != 2. head=2.
head=2, next=null. End.

java

public ListNode deleteDuplicates(ListNode head) {
    ListNode curr = head;
    while (curr != null && curr.next != null) {
        if (curr.val == curr.next.val) curr.next = curr.next.next;
        else curr = curr.next;
    }
    return head;
}

⚠️ Common Pitfalls & Tips

Only works on sorted lists. For unsorted lists, a hash set would be needed.

Approach 2

Level II: Recursive

Intuition

The recursive approach checks the head and its next node. If they have the same value, it skips the current head and returns the result of the recursive call on the next node.

⏱ O(N)💾 O(N) recursion stack

Detailed Dry Run

1->1->2.

head=1, next=1. Val 1 == 1. Return deleteDuplicates(1.next).
head=1, next=2. Val 1 != 2. head.next = deleteDuplicates(2). Return head.
head=2, next=null. Return head.

java

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) return head;
    head.next = deleteDuplicates(head.next);
    return head.val == head.next.val ? head.next : head;
}

⚠️ Common Pitfalls & Tips

Recursion depth is proportional to the number of nodes.

Approach 3

Level III: Iterative with Sentinel (Dummy Node)

Intuition

Using a dummy node isn't strictly necessary for this problem (since the head never changes), but it's a good practice to ensure consistency across all linked list problems.

Initialize a dummy node pointing to head.
Iterate through the list using a curr pointer.
Compare curr with curr.next and skip duplicates.

⏱ O(N)💾 O(1)

Detailed Dry Run

Dummy -> 1 -> 1 -> 2.

curr = 1. curr.next = 1. Match. curr.next = 2.
curr = 1. curr.next = 2. No match. curr = 2.
curr = 2. curr.next = null. End.

java

public ListNode deleteDuplicates(ListNode head) {
    if (head == null) return null;
    ListNode dummy = new ListNode(-101); // Constraint: val is usually -100 to 100
    dummy.next = head;
    ListNode curr = head;
    while (curr != null && curr.next != null) {
        if (curr.val == curr.next.val) curr.next = curr.next.next;
        else curr = curr.next;
    }
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

Ensure the dummy value doesn't conflict with valid node values.

Linked List Cycle II

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

Visual Representation

3 -> 2 -> 0 -> -4
     ^          |
     +----------+
Cycle starts at node with value 2.

Medium

Examples

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1

Approach 1

Level I: HashSet

Intuition

Store visited nodes in a set. The first node we encounter that is already in the set is the start of the cycle.

⏱ O(N)💾 O(N)

java

public ListNode detectCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    while (head != null) {
        if (visited.contains(head)) return head;
        visited.add(head); head = head.next;
    }
    return null;
}

Approach 2

Level II: Node Marking (Magic Value)

Intuition

If we can modify the node values, we can mark each visited node with a special value (outside the problem's constraints). If we encounter a node already marked with that value, it's the start of the cycle.

⏱ O(N)💾 O(1)

Detailed Dry Run

List: 3 -> 2 -> 0 -> -4 (back to 2).

3.val = 100001.
2.val = 100001.
0.val = 100001.
-4.val = 100001.
Next is 2, whose val is 100001. Cycle start found.

java

public ListNode detectCycle(ListNode head) {
    while (head != null) {
        if (head.val == 100001) return head;
        head.val = 100001; head = head.next;
    }
    return null;
}

⚠️ Common Pitfalls & Tips

This modifies the original list. In many real-world or interview scenarios, modifying the input data is not allowed unless specified.

Approach 3

Level III: Floyd's Cycle-Finding Algorithm

Intuition

Detect cycle first, then reset one pointer to head and move both at speed 1 to find meeting point.

Visual Trace

D = Distance to cycle, S = Meeting point from start, C = Cycle length.
Moving D steps from head and D steps from meeting point hits cycle start.

⏱ O(N)💾 O(1)

java

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
        if (slow == fast) {
            ListNode slow2 = head;
            while (slow2 != slow) { slow = slow.next; slow2 = slow2.next; }
            return slow;
        }
    }
    return null;
}

Remove Linked List Elements

Remove all nodes of the linked list that has Node.val == val.

Visual Representation

List: 1 -> 6 -> 2, val = 6
Result: 1 -> 2

Easy

Examples

Input: head = [1,2,3,6,4], val = 6
Output: [1,2,3,4]

Approach 1

Level I: Iterative

Intuition

Use a dummy node to handle head removal. Traverse and skip nodes matching val.

⏱ O(N)💾 O(1)

java

public ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(0, head), curr = dummy;
    while (curr.next != null) {
        if (curr.next.val == val) curr.next = curr.next.next;
        else curr = curr.next;
    }
    return dummy.next;
}

Approach 2

Level II: Recursive

Intuition

Process the rest of the list first. If the current head's value matches the target, return the processed rest; otherwise, link the current head to the processed rest and return the head.

⏱ O(N)💾 O(N) recursion stack

Detailed Dry Run

remove(1->6->2, 6).

head=1, next=remove(6->2, 6).
head=6, next=remove(2, 6).
head=2, next=remove(null, 6) returns null.
2.val != 6, returns 2.
6.val == 6, returns remove(2, 6) which is 2.
1.next = 2, returns 1.

java

public ListNode removeElements(ListNode head, int val) {
    if (head == null) return null;
    head.next = removeElements(head.next, val);
    return head.val == val ? head.next : head;
}

Odd Even Linked List

Group nodes with odd indices together followed by even indices.

Visual Representation

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

Medium

Examples

Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

Approach 1

Level I: Brute Force (Two Lists/Arrays)

Intuition

Traverse the list and store odd-indexed nodes in one list/array and even-indexed nodes in another. Then, link the end of the odd list to the head of the even list.

⏱ O(N)💾 O(N)

Detailed Dry Run

1->2->3->4. Odd: [1, 3]. Even: [2, 4]. Result: 1->3->2->4.

java

public ListNode oddEvenList(ListNode head) {
    if (head == null) return null;
    List<ListNode> odds = new ArrayList<>(), evens = new ArrayList<>();
    ListNode curr = head; int i = 1;
    while (curr != null) {
        if (i % 2 != 0) odds.add(curr);
        else evens.add(curr);
        curr = curr.next; i++;
    }
    for (int j = 0; j < odds.size() - 1; j++) odds.get(j).next = odds.get(j+1);
    for (int j = 0; j < evens.size() - 1; j++) evens.get(j).next = evens.get(j+1);
    if (!evens.isEmpty()) evens.get(evens.size() - 1).next = null;
    if (!odds.isEmpty()) odds.get(odds.size() - 1).next = evens.isEmpty() ? null : evens.get(0);
    return odds.get(0);
}

Approach 2

Level III: Two Pointers (In-place)

Intuition

Maintain odd and even pointers, cross-linking as you traverse.

⏱ O(N)💾 O(1)

java

public ListNode oddEvenList(ListNode head) {
    if (head == null) return null;
    ListNode odd = head, even = head.next, evenHead = even;
    while (even != null && even.next != null) {
        odd.next = even.next; odd = odd.next;
        even.next = odd.next; even = even.next;
    }
    odd.next = evenHead;
    return head;
}

Swap Nodes in Pairs

Swap every two adjacent nodes.

Visual Representation

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

Medium

Examples

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Approach 1

Level I: Recursive

Intuition

Swap first two nodes, recurse for the rest.

⏱ O(N)💾 O(N)

java

public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode next = head.next;
    head.next = swapPairs(next.next);
    next.next = head;
    return next;
}

Approach 2

Level III: Optimal (Iterative)

Intuition

Use a dummy node to simplify head swapping. Use a prev pointer to track the node before the current pair being swapped.

⏱ O(N)💾 O(1)

Detailed Dry Run

Dummy -> 1 -> 2 -> 3 -> 4. Prev = Dummy.

First = 1, Second = 2.
Prev.next = 2.
1.next = 3.
2.next = 1. Prev = 1.

java

public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0, head), prev = dummy;
    while (prev.next != null && prev.next.next != null) {
        ListNode first = prev.next, second = prev.next.next;
        first.next = second.next;
        second.next = first;
        prev.next = second;
        prev = first;
    }
    return dummy.next;
}

Rotate List

Rotate the list to the right by k places.

Visual Representation

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

Medium

Approach 1

Level III: Cycle + Break

Intuition

Form a cycle, find the new tail (n-k%n), and break.

⏱ O(N)💾 O(1)

java

public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null || k == 0) return head;
    ListNode tail = head; int n = 1;
    while (tail.next != null) { tail = tail.next; n++; }
    tail.next = head; k %= n;
    for (int i = 0; i < n - k; i++) tail = tail.next;
    head = tail.next; tail.next = null;
    return head;
}

Approach 2

Level II: Two Pointers

Intuition

Use two pointers, first and second. Move first k steps ahead. Then move both until first reaches the end. second will then be at the node before the new head.

⏱ O(N)💾 O(1)

Detailed Dry Run

1->2->3->4->5, k=2.

First moves 2 steps to 3.
Move both until First is at 5. Second is at 3.
New head = 3.next = 4.
3.next = null, 5.next = head.

java

public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null || k == 0) return head;
    ListNode fast = head, slow = head;
    int n = 0;
    while (fast != null) { fast = fast.next; n++; }
    k %= n; if (k == 0) return head;
    fast = head;
    for (int i = 0; i < k; i++) fast = fast.next;
    while (fast.next != null) { fast = fast.next; slow = slow.next; }
    ListNode newHead = slow.next;
    slow.next = null;
    fast.next = head;
    return newHead;
}

Convert Sorted List to BST

Convert a sorted linked list to a height-balanced BST.

Visual Representation

List: -10 -> -3 -> 0 -> 5 -> 9
Root is 0.

Medium

Approach 1

Level I: Brute Force (Convert to Array)

Intuition

Convert the linked list into an array. Then, use a standard recursive algorithm to convert the sorted array into a height-balanced BST by picking the middle element as the root.

⏱ O(N)💾 O(N)

Detailed Dry Run

List: -10, -3, 0, 5, 9. Array: [-10, -3, 0, 5, 9].

Root = 0.
Left = [-10, -3].
Right = [5, 9].

java

private List<Integer> values = new ArrayList<>();
public TreeNode sortedListToBST(ListNode head) {
    while (head != null) { values.add(head.val); head = head.next; }
    return buildBST(0, values.size() - 1);
}
private TreeNode buildBST(int left, int right) {
    if (left > right) return null;
    int mid = (left + right) / 2;
    TreeNode root = new TreeNode(values.get(mid));
    root.left = buildBST(left, mid - 1);
    root.right = buildBST(mid + 1, right);
    return root;
}

Approach 2

Level III: Recursive (Middle find)

Intuition

Use slow/fast pointers to find the middle (root), split, and recurse.

⏱ O(N log N)💾 O(log N)

java

public TreeNode sortedListToBST(ListNode head) {
    if (head == null) return null;
    if (head.next == null) return new TreeNode(head.val);
    ListNode prev = null, slow = head, fast = head;
    while (fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; }
    prev.next = null;
    TreeNode root = new TreeNode(slow.val);
    root.left = sortedListToBST(head);
    root.right = sortedListToBST(slow.next);
    return root;
}

← Previous TopicSliding Window

Next Topic →Binary Search

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.