Linked List — Worked Examples

# python
# LC 143 - Reorder List
# IDEA: first middle (fast/slow) -> cut -> reverse the back half -> interleave the two halves
# time = O(n), space = O(1)
class Solution(object):
    def reorderList(self, head):
        if not head or not head.next:
            return
        # 1) first middle: the left half is never the shorter one
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # 2) cut after the middle, then reverse the back half (Template 1)
        second = slow.next
        slow.next = None
        prev = None
        while second:
            nxt = second.next
            second.next = prev
            prev = second
            second = nxt

        # 3) interleave: one node from the front half, one from the reversed back half
        first, second = head, prev
        while second:
            first_next = first.next      # cache both successors before relinking
            second_next = second.next
            first.next = second
            second.next = first_next
            first = first_next
            second = second_next

// java
// LC 143 - Reorder List
// IDEA: first middle (fast/slow) -> cut -> reverse the back half -> interleave the two halves
// time = O(n), space = O(1)
public void reorderList(ListNode head) {
    if (head == null || head.next == null) {
        return;
    }
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    ListNode second = slow.next;
    slow.next = null;                       // cut: the halves must not share a node
    ListNode prev = null;
    while (second != null) {
        ListNode next = second.next;
        second.next = prev;
        prev = second;
        second = next;
    }

    ListNode first = head;
    second = prev;
    while (second != null) {
        ListNode firstNext = first.next;
        ListNode secondNext = second.next;
        first.next = second;
        second.next = firstNext;
        first = firstNext;
        second = secondNext;
    }
}

first middle:   slow = 3          front = 1 -> 2 -> 3     back = 4 -> 5
reverse back:                     back  = 5 -> 4
interleave:     1 -> 5 -> 2 -> 4 -> 3

# python
# LC 1019 - Next Greater Node In Linked List
# IDEA: list -> array, then a decreasing stack of indices; a larger value answers every index it pops
# time = O(n), space = O(n)
class Solution(object):
    def nextLargerNodes(self, head):
        vals = []
        while head:
            vals.append(head.val)
            head = head.next

        res = [0] * len(vals)           # 0 = no greater node
        stack = []                      # indices, values decreasing bottom -> top
        for i, v in enumerate(vals):
            while stack and vals[stack[-1]] < v:
                res[stack.pop()] = v
            stack.append(i)
        return res

// java
// LC 1019 - Next Greater Node In Linked List
// IDEA: list -> array, then a decreasing stack of indices; a larger value answers every index it pops
// time = O(n), space = O(n)
public int[] nextLargerNodes(ListNode head) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode cur = head; cur != null; cur = cur.next) {
        vals.add(cur.val);
    }
    int n = vals.size();
    int[] res = new int[n];                      // 0 = no greater node
    Deque<Integer> stack = new ArrayDeque<>();   // indices, values decreasing
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && vals.get(stack.peek()) < vals.get(i)) {
            res[stack.pop()] = vals.get(i);
        }
        stack.push(i);
    }
    return res;
}

i=0 v=2  stack=[0]
i=1 v=7  pop 0 (res[0]=7)                    stack=[1]
i=2 v=4                                      stack=[1,2]
i=3 v=3                                      stack=[1,2,3]
i=4 v=5  pop 3 (res[3]=5), pop 2 (res[2]=5)  stack=[1,4]
res = [7,0,5,5,0]

# python
# LC 19 - Remove Nth Node From End of List
# IDEA: start fast and slow on the dummy, open a gap of n + 1, walk both until fast falls off
# time = O(n), space = O(1)
class Solution(object):
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0)
        dummy.next = head
        fast = slow = dummy

        for _ in range(n + 1):        # the gap: slow will stop one node before the target
            fast = fast.next

        while fast:                   # walk both until fast falls off the end
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next    # unlink the target
        return dummy.next             # the head may have been the target

// java
// LC 19 - Remove Nth Node From End of List
// IDEA: start fast and slow on the dummy, open a gap of n + 1, walk both until fast falls off
// time = O(n), space = O(1)
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 + 1; i++) {
        fast = fast.next;
    }
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
}

fast = slow = dummy
fast moves n+1 = 6 steps:  dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None   (fast = None)
while fast: never runs     slow stays on dummy, one node before the head
slow.next = slow.next.next dummy -> 2 -> 3 -> 4 -> 5
return dummy.next          [2,3,4,5]

Without the dummy, slow starts ON the head: it can never stand before it, and
slow.next = slow.next.next removes 2 instead of 1 unless a special case returns head.next.

# python
# LC 147 - Insertion Sort List
# IDEA: detach each node and splice it into a dummy-headed sorted list after the last smaller node
# time = O(n^2), space = O(1)
class Solution(object):
    def insertionSortList(self, head):
        dummy = ListNode(0)              # sorted part: dummy.next onward
        cur = head
        while cur:
            nxt = cur.next               # detach cur: cache the rest first
            p = dummy
            while p.next and p.next.val < cur.val:
                p = p.next               # p = last sorted node smaller than cur
            cur.next = p.next            # splice cur after p
            p.next = cur
            cur = nxt
        return dummy.next

// java
// LC 147 - Insertion Sort List
// IDEA: detach each node and splice it into a dummy-headed sorted list after the last smaller node
// time = O(n^2), space = O(1)
public ListNode insertionSortList(ListNode head) {
    ListNode dummy = new ListNode(0);
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        ListNode p = dummy;
        while (p.next != null && p.next.val < cur.val) {
            p = p.next;
        }
        cur.next = p.next;
        p.next = cur;
        cur = next;
    }
    return dummy.next;
}

# python
# LC 1171 - Remove Zero Sum Consecutive Nodes from Linked List
# IDEA: prefix sum -> last node reaching it; second pass jumps from each prefix to its last occurrence
# time = O(n), space = O(n)
class Solution(object):
    def removeZeroSumSublists(self, head):
        dummy = ListNode(0, head)

        # pass 1: remember the LAST node reaching each prefix sum
        last_seen = {}
        prefix, cur = 0, dummy
        while cur:
            prefix += cur.val
            last_seen[prefix] = cur          # overwrite -> keeps the last one
            cur = cur.next

        # pass 2: from the first node with prefix p, jump past the last node with prefix p
        prefix, cur = 0, dummy
        while cur:
            prefix += cur.val
            cur.next = last_seen[prefix].next
            cur = cur.next
        return dummy.next

// java
// LC 1171 - Remove Zero Sum Consecutive Nodes from Linked List
// IDEA: prefix sum -> last node reaching it; second pass jumps from each prefix to its last occurrence
// time = O(n), space = O(n)
public ListNode removeZeroSumSublists(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    Map<Integer, ListNode> lastSeen = new HashMap<>();
    int prefix = 0;
    for (ListNode cur = dummy; cur != null; cur = cur.next) {
        prefix += cur.val;
        lastSeen.put(prefix, cur);
    }
    prefix = 0;
    for (ListNode cur = dummy; cur != null; cur = cur.next) {
        prefix += cur.val;
        cur.next = lastSeen.get(prefix).next;
    }
    return dummy.next;
}

node    : dummy  1   2   -3   3   1
prefix  :   0    1   3    0   3   4
last    : prefix 0 -> node -3,  prefix 3 -> node 3
pass 2  : dummy (0) jumps past -3  -> dummy -> 3
          3 (3)     jumps past 3   -> 3 -> 1
result  : [3,1]

# python
# LC 21 - Merge Two Sorted Lists
# IDEA: dummy + tail; splice the smaller head each step, then hang the leftover list on the tail
# time = O(m + n), space = O(1)
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        dummy = ListNode(0)
        tail = dummy                    # last node of the merged list
        while l1 and l2:
            if l1.val <= l2.val:        # <= keeps equal values in input order
                tail.next = l1          # splice the node itself, not a copy of its value
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        tail.next = l1 or l2            # one list is empty; the other is already sorted
        return dummy.next

# python
# LC 725 - Split Linked List in Parts
# IDEA: count n; part i gets n // k nodes, plus one when i < n % k; walk size - 1 nodes, then cut
# time = O(n + k), space = O(k) for the output
class Solution(object):
    def splitListToParts(self, head, k):
        length = 0
        node = head
        while node:
            length += 1
            node = node.next

        base, extra = divmod(length, k)
        parts = []
        cur = head
        for i in range(k):
            parts.append(cur)                      # None once the nodes run out
            size = base + (1 if i < extra else 0)
            if size == 0:
                continue
            for _ in range(size - 1):              # stand on the part's last node
                cur = cur.next
            nxt = cur.next
            cur.next = None                        # cut: terminate this part
            cur = nxt
        return parts

# python
# LC 817 - Linked List Components
# IDEA: a node in the set whose next is absent or outside the set ends one component
# time = O(n + len(nums)), space = O(len(nums))
class Solution(object):
    def numComponents(self, head, nums):
        in_set = set(nums)
        count = 0
        while head:
            run_ends = head.next is None or head.next.val not in in_set
            if head.val in in_set and run_ends:
                count += 1
            head = head.next
        return count

// java
// LC 817 - Linked List Components
// IDEA: a node in the set whose next is absent or outside the set ends one component
// time = O(n + nums.length), space = O(nums.length)
public int numComponents(ListNode head, int[] nums) {
    Set<Integer> inSet = new HashSet<>();
    for (int num : nums) {
        inSet.add(num);
    }
    int count = 0;
    for (ListNode cur = head; cur != null; cur = cur.next) {
        boolean runEnds = cur.next == null || !inSet.contains(cur.next.val);
        if (inSet.contains(cur.val) && runEnds) {
            count++;
        }
    }
    return count;
}

# python
# LC 24 - Swap Nodes in Pairs
# IDEA: the k = 2 case of the segment helper, unrolled; prev is the only cursor
# time = O(n), space = O(1)
class Solution(object):
    def swapPairs(self, head):
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy                  # node BEFORE the pair

        while prev.next and prev.next.next:
            first = prev.next         # becomes the pair's tail  (new_tail)
            second = first.next       # becomes the pair's front (new_head)

            first.next = second.next  # (A) carry next_node straight into the new tail
            second.next = first       # (B) flip the pair
            prev.next = second        # (C) prev adopts the new front

            prev = first              # new_tail sits before the next pair
        return dummy.next

dummy -> 1 -> 2 -> 3 -> 4         prev = dummy, first = 1, second = 2
(A) first.next  = second.next     1 -> 3
(B) second.next = first           2 -> 1
(C) prev.next   = second          dummy -> 2 -> 1 -> 3 -> 4
prev = first (1)                  next pair is 1.next, 1.next.next = (3, 4)
... same three links on (3, 4)    dummy -> 2 -> 1 -> 4 -> 3
prev.next.next is None -> stop    return [2,1,4,3]

# python
# LC 430 - Flatten a Multilevel Doubly Linked List
# IDEA: in-place splice: insert the child chain between cur and cur.next, then keep walking
# time = O(n), space = O(1)   each chain is tail-scanned once
class Solution(object):
    def flatten(self, head):
        cur = head
        while cur:
            if cur.child:
                nxt = cur.next                  # save the successor
                child = cur.child
                cur.child = None                # no child pointer may survive

                cur.next = child                # seam 1: cur <-> child
                child.prev = cur

                tail = child                    # last node of the child chain
                while tail.next:
                    tail = tail.next

                tail.next = nxt                 # seam 2: tail <-> nxt
                if nxt:
                    nxt.prev = tail
            cur = cur.next                      # walks INTO the spliced child
        return head

// java
// LC 430 - Flatten a Multilevel Doubly Linked List
// IDEA: in-place splice: insert the child chain between cur and cur.next, then keep walking
// time = O(n), space = O(1)   each chain is tail-scanned once
public Node flatten(Node head) {
    Node cur = head;
    while (cur != null) {
        if (cur.child != null) {
            Node next = cur.next;
            Node child = cur.child;
            cur.child = null;

            cur.next = child;
            child.prev = cur;

            Node tail = child;
            while (tail.next != null) {
                tail = tail.next;
            }
            tail.next = next;
            if (next != null) {
                next.prev = tail;
            }
        }
        cur = cur.next;
    }
    return head;
}

1 <-> 2 <-> 3 <-> 4
            |
            7 <-> 8 <-> 9
                  |
                  11 <-> 12

at node 3:  1 <-> 2 <-> 3 <-> 7 <-> 8 <-> 9 <-> 4
at node 8:  1 <-> 2 <-> 3 <-> 7 <-> 8 <-> 11 <-> 12 <-> 9 <-> 4

# python
# LC 25 - Reverse Nodes in k-Group
# IDEA: while k nodes remain after prev, reverse them with the helper and reconnect;
#       a final group shorter than k is left as it is
# time = O(n), space = O(1)
class Solution(object):
    def reverseKGroup(self, head, k):
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy                           # node before the current group

        while self.has_k(prev.next, k):
            new_head, new_tail, next_node = self.reverse_helper(prev.next, k)
            prev.next = new_head               # front of the group
            new_tail.next = next_node          # tail of the group -> rest
            prev = new_tail                    # the next group hangs off this tail
        return dummy.next

    def has_k(self, node, k):
        # are there at least k nodes starting at node?
        count = 0
        while node and count < k:
            node = node.next
            count += 1
        return count == k

    def reverse_helper(self, head, k):
        # reverse k nodes from head; return (new_head, new_tail, first node after)
        prev = None
        curr = head
        while curr and k > 0:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
            k -= 1
        return prev, head, curr

group 1: reverse 1,2   dummy -> 2 -> 1 -> 3 -> 4 -> 5    prev = 1
group 2: reverse 3,4   dummy -> 2 -> 1 -> 4 -> 3 -> 5    prev = 3
has_k(5, 2) is False   the short group [5] stays as it is
return [2,1,4,3,5]

# python
# LC 369 - Plus One Linked List
# IDEA: reverse, add a carry of 1 until it dies (appending a node if it survives), reverse back
# time = O(n), space = O(1)
class Solution(object):
    def plusOne(self, head):
        head = self.reverse(head)
        cur = head
        carry = 1
        while cur and carry:
            total = cur.val + carry
            cur.val = total % 10
            carry = total // 10
            if carry and cur.next is None:   # the carry outlives the last digit
                cur.next = ListNode(carry)
                carry = 0
            cur = cur.next
        return self.reverse(head)

    def reverse(self, head):
        prev = None
        while head:
            nxt = head.next
            head.next = prev
            prev = head
            head = nxt
        return prev

// java
// LC 369 - Plus One Linked List
// IDEA: reverse, add a carry of 1 until it dies (appending a node if it survives), reverse back
// time = O(n), space = O(1)
public ListNode plusOne(ListNode head) {
    head = reverse(head);
    ListNode cur = head;
    int carry = 1;
    while (cur != null && carry > 0) {
        int total = cur.val + carry;
        cur.val = total % 10;
        carry = total / 10;
        if (carry > 0 && cur.next == null) {
            cur.next = new ListNode(carry);
            carry = 0;
        }
        cur = cur.next;
    }
    return reverse(head);
}

private ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

# python
# LC 138 - Copy List with Random Pointer
# IDEA: pass 1 maps every old node to a new node; pass 2 wires next and random through the map
# time = O(n), space = O(n)
class Solution(object):
    def copyRandomList(self, head):
        old_to_new = {}
        cur = head
        while cur:                                   # pass 1: create every copy
            old_to_new[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while cur:                                   # pass 2: wire the copies
            old_to_new[cur].next = old_to_new.get(cur.next)      # None -> None
            old_to_new[cur].random = old_to_new.get(cur.random)
            cur = cur.next
        return old_to_new.get(head)

// java
// LC 138 - Copy List with Random Pointer
// IDEA: pass 1 maps every old node to a new node; pass 2 wires next and random through the map
// time = O(n), space = O(n)
public Node copyRandomList(Node head) {
    Map<Node, Node> oldToNew = new HashMap<>();
    for (Node cur = head; cur != null; cur = cur.next) {
        oldToNew.put(cur, new Node(cur.val));
    }
    for (Node cur = head; cur != null; cur = cur.next) {
        Node copy = oldToNew.get(cur);
        copy.next = oldToNew.get(cur.next);       // get(null) returns null
        copy.random = oldToNew.get(cur.random);
    }
    return oldToNew.get(head);
}