PK

PKBytes

Explore tracks
Chapter 11: Linked Lists
11.08Beginner / Intermediate6 topics20 min4 interactive animations

Advanced manipulations

Advanced list manipulations: stable partition around a value, rotation, swapping nodes in pairs, flattening a multi-level list, cloning a list with random pointers and the node management behind an LRU cache.

Learning goals

  • Rearrange nodes by relinking, never copying values
  • Rotate a list using a temporary ring
  • Clone a list with random pointers in O(1) extra pointers or with a map
  • Build an O(1) LRU cache from a hash map and a doubly linked list

Prerequisites

Reversal variantsLinked list mergingHash maps
11.08.1

Partition list

To partition a list around x so that nodes smaller than x come first while keeping the original order inside each part, build two chains with dummy heads (a “less” chain and a “more” chain), append each node to the right chain, then link the chains and cut the end of the second so it points to null. A single pass, O(n) time, O(1) extra space, and the result is stable.

Cutting the end (more.next = null) is the step people forget; without it the list can form a cycle.

Java
1static Node partition(Node head, int x) {
2    Node lessHead = new Node(0), moreHead = new Node(0), less = lessHead, more = moreHead;
3    for (Node cur = head; cur != null; cur = cur.next) {
4        if (cur.val < x) { less.next = cur; less = cur; }
5        else             { more.next = cur; more = cur; }
6    }
7    more.next = null;                  // cut the old tail link
8    less.next = moreHead.next;         // join
9    return lessHead.next;
10}

Partition, rotate and swap pairs by relinking

Interactive · edit the input

Your input

Try

linked list · 6 nodes

1
4
3
2
5
2
null
head
Node being handledIn the first partIn the second part
Setup

Split into two chains: values < 3 and values >= 3, each in original order, then join them.

Step 1 / 9
Java
1static Node partition(Node head, int x) {                    // nodes < x first, then the rest; stable
2    Node lessHead = new Node(0), moreHead = new Node(0), less = lessHead, more = moreHead;
3    for (Node cur = head; cur != null; cur = cur.next) {
4        if (cur.val < x) { less.next = cur; less = cur; }
5        else             { more.next = cur; more = cur; }
6    }
7    more.next = null;                                          // cut the old tail link
8    less.next = moreHead.next;                                 // join the two chains
9    return lessHead.next;
10}
11static Node rotateRight(Node head, int k) {
12    if (head == null || head.next == null || k == 0) return head;
13    int n = 1; Node tail = head; while (tail.next != null) { tail = tail.next; n++; }
14    tail.next = head;                                          // close the list into a ring
15    Node newTail = head; for (int i = 0; i < n - k % n - 1; i++) newTail = newTail.next;
16    Node newHead = newTail.next; newTail.next = null;           // cut the ring after the new tail
17    return newHead;
18}
19static Node swapPairs(Node head) {
20    Node dummy = new Node(0); dummy.next = head; Node prev = dummy;
21    while (prev.next != null && prev.next.next != null) {
22        Node a = prev.next, b = a.next;
23        a.next = b.next; b.next = a; prev.next = b;            // relink the pair
24        prev = a;
25    }
26    return dummy.next;
27}

Live state

n

6

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L2n=6Split into two chains: values < 3 and values >= 3, each in original order, then join them.
2L4cur=11 < 3: append to the "less" chain.
3L5cur=44 >= 3: append to the "more" chain.
4L5cur=33 >= 3: append to the "more" chain.
5L4cur=22 < 3: append to the "less" chain.
6L5cur=55 >= 3: append to the "more" chain.
7L4cur=22 < 3: append to the "less" chain.
8L7more.next = null: the last node of the second chain must not point back into the first.
9L8return=[1, 2, 2, 4, 3, 5]Joined: [1, 2, 2, 4, 3, 5]. Both chains kept their original order, so the partition is stable. O(n) time, O(1) extra space.
11.08.2

Rotate list

Rotating right by k moves the last k nodes to the front. Walk to the tail while counting the length n, link the tail to the head to form a ring, walk n - k mod n - 1 steps from the head to find the new tail, then cut the ring after it. Reduce k modulo n first, because rotating by n changes nothing. O(n) time, O(1) space.

Try k larger than the length.

Java
1static Node rotateRight(Node head, int k) {
2    if (head == null || head.next == null || k == 0) return head;
3    int n = 1; Node tail = head;
4    while (tail.next != null) { tail = tail.next; n++; }
5    tail.next = head;                                    // make a ring
6    Node newTail = head;
7    for (int i = 0; i < n - k % n - 1; i++) newTail = newTail.next;
8    Node newHead = newTail.next;
9    newTail.next = null;                                 // cut the ring
10    return newHead;
11}

Partition, rotate and swap pairs by relinking

Interactive · edit the input

Your input

Try

linked list · 6 nodes

1
4
3
2
5
2
null
head
Node being handledIn the first partIn the second part
Setup

Split into two chains: values < 3 and values >= 3, each in original order, then join them.

Step 1 / 9
Java
1static Node partition(Node head, int x) {                    // nodes < x first, then the rest; stable
2    Node lessHead = new Node(0), moreHead = new Node(0), less = lessHead, more = moreHead;
3    for (Node cur = head; cur != null; cur = cur.next) {
4        if (cur.val < x) { less.next = cur; less = cur; }
5        else             { more.next = cur; more = cur; }
6    }
7    more.next = null;                                          // cut the old tail link
8    less.next = moreHead.next;                                 // join the two chains
9    return lessHead.next;
10}
11static Node rotateRight(Node head, int k) {
12    if (head == null || head.next == null || k == 0) return head;
13    int n = 1; Node tail = head; while (tail.next != null) { tail = tail.next; n++; }
14    tail.next = head;                                          // close the list into a ring
15    Node newTail = head; for (int i = 0; i < n - k % n - 1; i++) newTail = newTail.next;
16    Node newHead = newTail.next; newTail.next = null;           // cut the ring after the new tail
17    return newHead;
18}
19static Node swapPairs(Node head) {
20    Node dummy = new Node(0); dummy.next = head; Node prev = dummy;
21    while (prev.next != null && prev.next.next != null) {
22        Node a = prev.next, b = a.next;
23        a.next = b.next; b.next = a; prev.next = b;            // relink the pair
24        prev = a;
25    }
26    return dummy.next;
27}

Live state

n

6

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L2n=6Split into two chains: values < 3 and values >= 3, each in original order, then join them.
2L4cur=11 < 3: append to the "less" chain.
3L5cur=44 >= 3: append to the "more" chain.
4L5cur=33 >= 3: append to the "more" chain.
5L4cur=22 < 3: append to the "less" chain.
6L5cur=55 >= 3: append to the "more" chain.
7L4cur=22 < 3: append to the "less" chain.
8L7more.next = null: the last node of the second chain must not point back into the first.
9L8return=[1, 2, 2, 4, 3, 5]Joined: [1, 2, 2, 4, 3, 5]. Both chains kept their original order, so the partition is stable. O(n) time, O(1) extra space.
11.08.3

Swap pairs

Swapping adjacent pairs by relinking (not by swapping values, which interviewers often forbid) uses a dummy head and a prev pointer. For each pair a, b: a.next = b.next; b.next = a; prev.next = b; then move prev to a. An unpaired last node stays where it is. O(n) time, O(1) space.

Choose Swap nodes in pairs.

Java
1static Node swapPairs(Node head) {
2    Node dummy = new Node(0); dummy.next = head;
3    Node prev = dummy;
4    while (prev.next != null && prev.next.next != null) {
5        Node a = prev.next, b = a.next;
6        a.next = b.next;
7        b.next = a;
8        prev.next = b;
9        prev = a;
10    }
11    return dummy.next;
12}

Partition, rotate and swap pairs by relinking

Interactive · edit the input

Your input

Try

linked list · 6 nodes

1
4
3
2
5
2
null
head
Node being handledIn the first partIn the second part
Setup

Split into two chains: values < 3 and values >= 3, each in original order, then join them.

Step 1 / 9
Java
1static Node partition(Node head, int x) {                    // nodes < x first, then the rest; stable
2    Node lessHead = new Node(0), moreHead = new Node(0), less = lessHead, more = moreHead;
3    for (Node cur = head; cur != null; cur = cur.next) {
4        if (cur.val < x) { less.next = cur; less = cur; }
5        else             { more.next = cur; more = cur; }
6    }
7    more.next = null;                                          // cut the old tail link
8    less.next = moreHead.next;                                 // join the two chains
9    return lessHead.next;
10}
11static Node rotateRight(Node head, int k) {
12    if (head == null || head.next == null || k == 0) return head;
13    int n = 1; Node tail = head; while (tail.next != null) { tail = tail.next; n++; }
14    tail.next = head;                                          // close the list into a ring
15    Node newTail = head; for (int i = 0; i < n - k % n - 1; i++) newTail = newTail.next;
16    Node newHead = newTail.next; newTail.next = null;           // cut the ring after the new tail
17    return newHead;
18}
19static Node swapPairs(Node head) {
20    Node dummy = new Node(0); dummy.next = head; Node prev = dummy;
21    while (prev.next != null && prev.next.next != null) {
22        Node a = prev.next, b = a.next;
23        a.next = b.next; b.next = a; prev.next = b;            // relink the pair
24        prev = a;
25    }
26    return dummy.next;
27}

Live state

n

6

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L2n=6Split into two chains: values < 3 and values >= 3, each in original order, then join them.
2L4cur=11 < 3: append to the "less" chain.
3L5cur=44 >= 3: append to the "more" chain.
4L5cur=33 >= 3: append to the "more" chain.
5L4cur=22 < 3: append to the "less" chain.
6L5cur=55 >= 3: append to the "more" chain.
7L4cur=22 < 3: append to the "less" chain.
8L7more.next = null: the last node of the second chain must not point back into the first.
9L8return=[1, 2, 2, 4, 3, 5]Joined: [1, 2, 2, 4, 3, 5]. Both chains kept their original order, so the partition is stable. O(n) time, O(1) extra space.
11.08.4

Flatten multi-level list

In a multi-level list each node may also have a child pointer to another list. Flattening puts the child list between the node and its next, recursively. Use a stack for the pending next nodes, or walk the list and splice each child in front of the remaining list. O(n) over all nodes.

The same idea flattens nested iterators and menu trees.

Java
1class MNode { int val; MNode next, child; MNode(int v) { val = v; } }
2static MNode flatten(MNode head) {
3    for (MNode cur = head; cur != null; cur = cur.next) {
4        if (cur.child == null) continue;
5        MNode child = cur.child, tail = child;
6        while (tail.next != null) tail = tail.next;       // last node of the child list
7        tail.next = cur.next;                              // child list continues into the old next
8        cur.next = child; cur.child = null;
9    }
10    return head;
11}
11.08.5

Clone random-pointer list

A list whose nodes also have a random pointer to any node (or null) cannot be cloned by copying nodes in order, because a random target may not exist yet. Two standard solutions: a hash map from original node to copy (O(n) space), or interleave each copy right after its original, set copy.random = original.random.next, and then split the lists apart (O(1) extra space).

The interleaving trick avoids the map by using the list itself as the lookup table.

Java
1class RNode { int val; RNode next, random; RNode(int v) { val = v; } }
2static RNode copyRandomList(RNode head) {
3    Map<RNode, RNode> copy = new HashMap<>();
4    for (RNode cur = head; cur != null; cur = cur.next) copy.put(cur, new RNode(cur.val));
5    for (RNode cur = head; cur != null; cur = cur.next) {
6        copy.get(cur).next = cur.next == null ? null : copy.get(cur.next);
7        copy.get(cur).random = cur.random == null ? null : copy.get(cur.random);
8    }
9    return head == null ? null : copy.get(head);
10}
11.08.6

LRU node management

An LRU (least recently used) cache needs O(1) lookup, O(1) “mark as most recent” and O(1) eviction of the oldest. A hash map finds a key's node, and a doubly linked list keeps the keys ordered by recency: on a hit unlink the node and insert it at the front, on a miss insert at the front and evict the tail node if the capacity is exceeded. The doubly linked list makes unlinking an arbitrary node O(1). LinkedHashMap with access order implements exactly this.

Run the access sequence and watch hits move nodes to the front.

Java
1static class LRU<K, V> extends LinkedHashMap<K, V> {
2    private final int capacity;
3    LRU(int capacity) { super(16, 0.75f, true); this.capacity = capacity; }        // true = access order
4    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; }
5}

LRU cache: hash map + doubly linked list

Interactive · edit the input

Your input

Try

most recent → least recent · 0 nodes

null
Accessed nowHitEvicted

map: key → node

empty
Setup

A cache of capacity 3. The list keeps keys from most to least recently used; the hash map finds a key's node in O(1).

Step 1 / 18
Java
1class LRUCache {
2    private final int capacity;
3    private final Map<Integer, DNode> map = new HashMap<>();      // key -> node: O(1) lookup
4    private final DNode head = new DNode(), tail = new DNode();    // head.next is the most recently used
5    boolean access(int key) {
6        DNode node = map.get(key);
7        if (node != null) { unlink(node); addFirst(node); return true; }       // hit: move to the front
8        node = new DNode(key); map.put(key, node); addFirst(node);              // miss: insert at the front
9        if (map.size() > capacity) { DNode lru = tail.prev; unlink(lru); map.remove(lru.key); }   // evict the oldest
10        return false;
11    }
12}

Live state

capacity

3

No condition evaluated on this step
Execution trace (dry run table)Show 18 steps
StepLineStateWhat happens
1L4capacity=3A cache of capacity 3. The list keeps keys from most to least recently used; the hash map finds a key's node in O(1).
2L8access=1 hits=0 misses=1Access 1: miss. Insert a new node at the front and record it in the map.
3L8access=2 hits=0 misses=2Access 2: miss. Insert a new node at the front and record it in the map.
4L8access=3 hits=0 misses=3Access 3: miss. Insert a new node at the front and record it in the map.
5L7access=1 hits=1 misses=3Access 1: hit. Unlink its node and re-insert it at the front (O(1) because the node knows both neighbours).
6L8access=4 hits=1 misses=4Access 4: miss. Insert a new node at the front and record it in the map.
7L9evict=2The cache holds 4 > 3 keys: evict the least recently used, 2, from the tail and from the map.
8L9size=32 is gone.
9L8access=2 hits=1 misses=5Access 2: miss. Insert a new node at the front and record it in the map.
10L9evict=3The cache holds 4 > 3 keys: evict the least recently used, 3, from the tail and from the map.
11L9size=33 is gone.
12L8access=5 hits=1 misses=6Access 5: miss. Insert a new node at the front and record it in the map.
13L9evict=1The cache holds 4 > 3 keys: evict the least recently used, 1, from the tail and from the map.
14L9size=31 is gone.
15L8access=1 hits=1 misses=7Access 1: miss. Insert a new node at the front and record it in the map.
16L9evict=4The cache holds 4 > 3 keys: evict the least recently used, 4, from the tail and from the map.
17L9size=34 is gone.
18L12hits=1 misses=7 return=[1, 5, 2]1 hit and 7 misses out of 8 accesses. Final order, most recent first: [1, 5, 2]. Every operation is O(1).

Practice ladder

Now try it yourself

Easy

  • Partition 1 → 4 → 3 → 2 → 5 → 2 around 3
  • Rotate 1 → 2 → 3 → 4 → 5 right by 2

Medium

  • Swap pairs in 1 → 2 → 3 → 4 → 5
  • Clone a list with random pointers using a HashMap

Advanced

  • Implement an LRU cache with your own doubly linked list and a HashMap

Key takeaways

  • Rearrange by relinking: two chains for partition, a ring for rotation, a dummy head for pairs.
  • Clone with a map or by interleaving copies.
  • LRU = hash map + doubly linked list for O(1) everything.