鏈結串列 — 範例題解

// java

  // V0-1
  // IDEA: LINKED LIST OP (iteration 1)
  // https://neetcode.io/solutions/reverse-linked-list-ii
  // https://youtu.be/RF_M9tX4Eag?si=vTfAtfbmGwzsmtpi
  public ListNode reverseBetween_0_1(ListNode head, int left, int right) {
      ListNode dummy = new ListNode(0);
      dummy.next = head;
      ListNode leftPrev = dummy, cur = head;

      for (int i = 0; i < left - 1; i++) {
          leftPrev = cur;
          cur = cur.next;
      }

      ListNode prev = null;
      for (int i = 0; i < right - left + 1; i++) {
          ListNode tmpNext = cur.next;
          cur.next = prev;
          prev = cur;
          cur = tmpNext;
      }

      leftPrev.next.next = cur;
      leftPrev.next = prev;

      return dummy.next;
  }

// java
    public void reorderList(ListNode head) {
        // Edge case: empty or single node list
        if (head == null || head.next == null) {
            return;
        }

        // Step 1: Find the middle node
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Step 2: Reverse the second half of the list
        /** NOTE !!!
         *
         *  reverse on `slow.next` node
         */
        ListNode secondHalf = reverseNode_(slow.next);
        /** NOTE !!!
         *
         *  `cut off` slow node's next nodes via point it to null node
         *  (if not cut off, then in merge step, we will merge duplicated nodes
         */
        slow.next = null; // Break the list into two halves

        // Step 3: Merge two halves
        ListNode firstHalf = head;
        while (secondHalf != null) {

            // NOTE !!! cache `next node` before any op
            ListNode _nextFirstHalf = firstHalf.next;
            ListNode _nextSecondHalf = secondHalf.next;

            // NOTE !!! point first node to second node, then point second node to first node's next node
            firstHalf.next = secondHalf;
            secondHalf.next = _nextFirstHalf;

            // NOTE !!! move both node to `next` node
            firstHalf = _nextFirstHalf;
            secondHalf = _nextSecondHalf;
        }
    }

    // Helper function to reverse a linked list
    private ListNode reverseNode_(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

# LC 143. Reorder List
# V0
# IDEA : Reverse the Second Part of the List and Merge Two Sorted Lists
class Solution:
    def reorderList(self, head):
        if not head:
            return 
        
        # find the middle of linked list [Problem 876]
        # in 1->2->3->4->5->6 find 4 
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next 
            
        # reverse the second part of the list [Problem 206]
        # convert 1->2->3->4->5->6 into 1->2->3->4 and 6->5->4
        # reverse the second half in-place
        prev, curr = None, slow
        while curr:
            tmp = curr.next
            
            curr.next = prev
            prev = curr
            curr = tmp    

        # merge two sorted linked lists [Problem 21]
        # merge 1->2->3->4 and 6->5->4 into 1->6->2->5->3->4
        first, second = head, prev
        while second.next:
            tmp = first.next
            first.next = second
            first = tmp
            
            tmp = second.next
            second.next = first
            second = tmp

# V0'
# IDEA : Reverse the Second Part of the List and Merge Two Sorted Lists (simplified code from V1)
class Solution:
    def reorderList(self, head):
        if not head:
            return 
        
        # find the middle of linked list [Problem 876]
        # in 1->2->3->4->5->6 find 4 
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next 
            
        # reverse the second part of the list [Problem 206]
        # convert 1->2->3->4->5->6 into 1->2->3->4 and 6->5->4
        # reverse the second half in-place
        prev, curr = None, slow
        while curr:
            curr.next, prev, curr = prev, curr, curr.next       

        # merge two sorted linked lists [Problem 21]
        # merge 1->2->3->4 and 6->5->4 into 1->6->2->5->3->4
        first, second = head, prev
        while second.next:
            first.next, first = second, first.next
            second.next, second = first, second.next

# V0'''
class Solution:
    def reorderList(self, head):
        if head is None:
            return head

        #find mid
        slow = head
        fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow

        #cut in the mid
        left = head
        right = mid.next
        if right is None:
            return head
        mid.next = None

        #reverse right half
        cursor = right.next
        right.next = None
        while cursor:
            next = cursor.next
            cursor.next = right
            right = cursor
            cursor = next
        
        #merge left and right
        dummy = ListNode(0)
        while left or right:
            if left is not None:
                dummy.next = left
                left = left.next
                dummy = dummy.next
            if right is not None:
                dummy.next = right
                right = right.next
                dummy = dummy.next
        return head

prev -> first -> second -> (rest...)

prev -> second -> first -> (rest...)

# LC 24. Swap Nodes in Pairs  (the version we walk through)
# time = O(n), space = O(1)
class Solution(object):
    def swapPairs(self, head):
        if not head or not head.next:
            return head

        dummy = ListNode(0)
        dummy.next = head
        prev = dummy                 # node BEFORE the current pair

        while head and head.next:
            first  = head            # 1st node of the pair
            second = head.next        # 2nd node of the pair

            # ---- reconnect (3 links) ----
            first.next  = second.next  # (A) first jumps OVER second, to the rest
            second.next = first        # (B) second now points back to first  -> pair flipped
            prev.next   = second       # (C) prev adopts second as the new front

            # ---- advance ----
            prev = first             # first is now the tail of this pair -> becomes next `prev`
            head = first.next         # move head to the start of the next pair
        return dummy.next

Start:   prev=dummy, first=1, second=2
         dummy -> [1] -> [2] -> 3 -> 4
          prev   first  second  rest=3

(A) first.next = second.next   # 1.next = 3   (1 jumps over 2, onto 3)
         dummy -> [1] --------> 3 -> 4
                  [2] -> 3           (2 still points at 3 for now)
          prev=dummy, second=2 dangling in front

(B) second.next = first        # 2.next = 1   (flip: 2 -> 1)
         dummy    [2] -> [1] -> 3 -> 4
          prev

(C) prev.next = second         # dummy.next = 2   (front adopts new head)
         dummy -> [2] -> [1] -> 3 -> 4   ✓ pair swapped!

Advance: prev = first(1) ;  head = first.next = 3
         dummy -> 2 -> [1] -> [3] -> 4
                       prev  head  ...   → next loop swaps (3,4)

while head and head.next:
    first  = head
    second = head.next
    first.next  = second.next   # (A)
    second.next = first         # (B)
    prev.next   = second        # (C)
    prev = first                # advance
    head = first.next           # advance

dummy -> 1 -> 2 -> 3 -> 4 -> None
 prev   head

cache:  first = 1 ,  second = 2 ,  (second.next = 3 = "rest")

(A) first.next  = second.next   # 1.next = 3
        dummy -> 1 -> 3 -> 4        (2 temporarily off to the side, still 2->3)
(B) second.next = first         # 2.next = 1
        2 -> 1 -> 3 -> 4           (pair flipped internally)
(C) prev.next   = second        # dummy.next = 2
        dummy -> 2 -> 1 -> 3 -> 4  ✓ (1,2) swapped

advance: prev = first  = 1
         head = first.next = 3

dummy -> 2 -> 1 -> 3 -> 4 -> None
              prev head

cache:  first = 3 ,  second = 4 ,  (second.next = None = "rest")

(A) first.next  = second.next   # 3.next = None
        ... 1 -> 3 -> None
(B) second.next = first         # 4.next = 3
        4 -> 3 -> None
(C) prev.next   = second        # (prev=1).next = 4
        ... 1 -> 4 -> 3 -> None  ✓ (3,4) swapped

advance: prev = first  = 3
         head = first.next = None

dummy -> 2 -> 1 -> 4 -> 3 -> None
                   prev head=None

return dummy.next  =>  2 -> 1 -> 4 -> 3   ✓

# V0' — same idea, `head` acts as `prev`
class Solution:
    def swapPairs(self, head):
        if not head or not head.next:
            return head
        dummy = ListNode(0)
        dummy.next = head
        head = dummy                 # head plays the `prev` role
        while head.next and head.next.next:
            n1, n2 = head.next, head.next.next   # n1=first, n2=second
            n1.next   = n2.next   # (A) first over second
            n2.next   = n1        # (B) flip
            head.next = n2        # (C) prev -> second
            head = n1             # advance prev to tail of swapped pair
        return dummy.next

# time = O(n), space = O(n)  (call stack)
class Solution(object):
    def swapPairs(self, head):
        if not head or not head.next:      # base: 0 or 1 node -> nothing to swap
            return head
        first, second = head, head.next
        first.next  = self.swapPairs(second.next)  # (A) first -> swapped rest
        second.next = first                        # (B) flip pair
        return second                              # (C) second is the new head of this segment

# LC 021
# V0
# IDEA : LOOP 2 LINKED LISTS
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        if not l1 or not l2:
            return l1 or l2
        ### NOTICE THIS
        #   -> we init head, and cur
        #   -> use cur for `link` op
        #   -> and return the `head.next`
        head = cur = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                """
                ### NOTE
                 1) assign node to cur.next !!! (not cur)
                 2) assign node rather than node.val
                """ 
                cur.next = l1
                l1 = l1.next
            else:
                """
                ### NOTE
                 1) assign node to cur.next !!! (not cur)
                 2) assign node rather than node.val
                """ 
                cur.next = l2
                l2 = l2.next
            # note this
            cur = cur.next
        ### NOTE this (in case either l1 or l2 is remaining so we need to append one of them to cur)
        cur.next = l1 or l2
        ### NOTICE THIS : we return head.next
        return head.next

# LC 023 Merge k sorted lists
# V0
# IDEA : LC 021 Merge Two Sorted Lists + implement mergeTwoLists on every 2 linedlist
# see 4) Merge Two Sorted Lists above for the mergeTwoLists half of this
class Solution(object):
    def mergeKLists(self, lists):
        if len(lists) == 0:
            return
        if len(lists) == 1:
            return lists[0]
        
        _init_list = lists[0]
        for _list in lists[1:]:
            tmp = self.mergeTwoLists(_init_list, _list)
            _init_list = tmp
        return tmp

    # LC 021 : https://github.com/yennanliu/CS_basics/blob/master/leetcode_python/Linked_list/merge-two-sorted-lists.py
    def mergeTwoLists(self, l1, l2):

        if not l1 or not l2:
            return l1 or l2
            
        res = head = ListNode()
        while l1 and l2:
            if l1.val < l2.val:
                res.next = l1
                l1 = l1.next
            else:
                res.next = l2
                l2 = l2.next
            res = res.next

        if l1 or l2:
            res.next = l1 or l2

        return head.next

# LC 725. Split Linked List in Parts
# V0
# IDEA : LINKED LIST OP + mod op
class Solution(object):
    def splitListToParts(self, head, k):
        # NO need to deal with edge case !!!
        # get linked list length
        _len = 0
        _head = cur = head
        while _head:
            _len += 1
            _head = _head.next
        # init res
        res = [None] * k
        ### NOTE : we loop over k
        for i in range(k):
            """
            2 cases

            case 1) i < (_len % k) : there is "remainder" ((_len % k)), so we need to add extra 1
                    -> _cnt_elem = (_len // k) + 1
            case 2) i == (_len % k) : there is NO "remainder"
                    -> _cnt_elem = (_len // k)
            """
            # NOTE THIS !!!
            _cnt_elem = (_len // k) + (1 if i < (_len % k) else 0)
            ### NOTE : we loop over _cnt_elem (length of each "split" linkedlist)
            for j in range(_cnt_elem):
                """
                3 cases
                 1) j == 0                (begin of sub linked list)
                 2) j == _cnt_elem - 1    (end of sub linked list)
                 3) 0 < j < _cnt_elem - 1 (middle within sub linked list)
                """
                # NOTE THIS !!!
                # NOTE we need keep if - else in BELOW ORDER !!
                #  -> j == 0, j == _cnt_elem - 1, else
                if j == 0:
                    res[i] = cur
                ### NOTE this !!! : 
                #    -> IF (but not elif)
                #    -> since we also need to deal with j == 0 and j == _cnt_elem - 1 case
                if j == _cnt_elem - 1:  # note this !!!
                    # get next first
                    tmp = cur.next
                    # point cur.next to None
                    cur.next = None
                    # move cur to next (tmp) for op in next i (for i in range(k))
                    cur = tmp
                else:
                    cur = cur.next
        #print ("res = " + str(res))
        return res

# LC 234 : palindrome-linked-list
# V0
# IDEA : LINKED LIST -> LIST
# EXAMPLE INPUT :
# [1,2,2,1]
# WHILE GO THROUGH :
# head = ListNode{val: 2, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}
# head = ListNode{val: 2, next: ListNode{val: 1, next: None}}
# head = ListNode{val: 1, next: None}
class Solution(object):
    def isPalindrome(self, head):
        ### NOTE : THE CONDITION
        if not head or not head.next:
            return True
        r = []
        ### NOTE : THE CONDITION
        while head:
            r.append(head.val)
            head = head.next
        return r == r[::-1]

# LC 160 Intersection of Two Linked Lists
# V0
# IDEA : if the given 2 linked list have intersection, then 
#        they must overlap in SOMEWHERE if we go through
#        each of them in the same length
#        -> e.g.
#             process1 : headA -> headB -> headA ...
#             process2 : headB -> headA -> headB ...
class Solution(object):
    def getIntersectionNode(self, headA, headB):
        if not headA or not headB:
            return None
        p, q = headA, headB
        while p and q and p != q:
            p = p.next
            q = q.next
            if p == q:
                return p
            if not p:
                p = headB
            if not q:
                q = headA
        return p

// java
    public ListNode removeNthFromEnd(ListNode head, int n) {

        if (head == null){
            return head;
        }

        if (head.next == null && head.val == n){
            return null;
        }

        // move fast pointer only with n+1 step
        // 2 cases:
        //   - 1) node count is even
        //   - 2) node count is odd
        /** NOTE !! we init dummy pointer, and let fast, slow pointers point to it */
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // NOTE here
        ListNode fast = dummy;
        ListNode slow = dummy;
        /**
         *  Explanation V1:
         *
         *   -> So we have fast, and slow pointer,
         *   if we move fast N steps first,
         *   then slow starts to move
         *      -> fast, slow has N step difference
         *      -> what's more, when fast reach the end,
         *      -> fast, slow STILL has N step difference
         *      -> and slow has N step difference with the end,
         *      -> so we can remove N th pointer accordingly
         *
         *  Explanation V2:
         *
         *
         *   // NOTE !!! we let fast pointer move N+1 step first
         *   // so once fast pointers reach the end after fast, slow pointers move together
         *   // we are sure that slow pointer is at N-1 node
         *   // so All we need to do is :
         *   // point slow.next to slow.next.next
         *   // then we remove N node from linked list
         */
        for (int i = 1; i <= n+1; i++){
            //System.out.println("i = " + i);
            fast = fast.next;
        }

        // move fast and slow pointers on the same time
        while (fast != null){
            fast = fast.next;
            slow = slow.next;
        }

        // NOTE here
        slow.next = slow.next.next;
        // NOTE !!! we return dummy.next instead of slow
        return dummy.next;
    }

// java
    // V0
    // IDEA : get len of linkedlist, and re-point node
    public ListNode removeNthFromEnd_0(ListNode head, int n) {

        if (head.next == null){
            return null;
        }

        // below op is optional
//        if (head.next.next == null){
//            if (n == 1){
//                return new ListNode(head.val);
//            }
//            return new ListNode(head.next.val);
//        }

        // get len
        int len = 0;
        ListNode head_ = head;
        while (head_ != null){
            head_ = head_.next;
            len += 1;
        }

        ListNode root = new ListNode();
        /** NOTE !!! root_ is the actual final result */
        ListNode root_ = root;

        // if n == len
        if (n == len){
            head = head.next;
            root.next = head;
            root = root.next;
        }

        /**
         *  IDEA: get length of linked list,
         *        then if want to delete n node from the end of linked list,
         *        -> then we need to stop at "len - n" idx,
         *        -> and reconnect "len - n" idx to "len -n + 2" idx
         *        -> (which equals delete "n" idx node
         *
         *
         *  Consider linked list below :
         *
         *   0, 1, 2 , 3, 4 .... k-2, k-1, k
         *
         *   if n = 1, then "k-1" is the node to be removed.
         *   -> so we find "k-2" node, and re-connect it to "k" node
         */
        /** NOTE !!!
         *
         *  idx is the index, that we "stop",  and re-connect
         *  from idx to its next next node (which is the actual "delete" node op
         */
        int idx = len - n; // NOTE !!! this
        while (idx > 0){
            root.next = head;
            root = root.next;
            head = head.next;
            idx -= 1;
        }

        ListNode next = head.next;
        root.next = next;

        return root_.next;
    }

# LC 138. Copy List with Random Pointer
# V0
# IDEA : 
#   step 1) make 2 objects (m, n) refer to same instance (head)
#   step 2) go through m, and set up the dict
#   step 3) go through n, and get the random pointer via the dict we set up in step 2)
class Node(object):
    def __init__(self, val, next, random):
        self.val = val
        self.next = next
        self.random = random

class Solution:
    def copyRandomList(self, head):
        dic = dict()
        ### NOTE : make m, and n refer to same instance (head)
        m = n = head
        while m:
            ### NOTE : the value in dict is Node type (LinkedList)
            dic[m] = Node(m.val)
            m = m.next
        while n:
            dic[n].next = dic.get(n.next)
            dic[n].random = dic.get(n.random)
            n = n.next
        return dic.get(head)

// java
// NOTE : there is also recursive solution
// LC 138
// V2
// IDEA :  Iterative with O(N) Space
// https://leetcode.com/problems/copy-list-with-random-pointer/editorial/
// Visited dictionary to hold old node reference as "key" and new node reference as the "value"
HashMap<Node, Node> visited = new HashMap<Node, Node>();

public Node getClonedNode(Node node) {
    // If the node exists then
    if (node != null) {
        // Check if the node is in the visited dictionary
        if (this.visited.containsKey(node)) {
            // If its in the visited dictionary then return the new node reference from the dictionary
            return this.visited.get(node);
        } else {
            // Otherwise create a new node, add to the dictionary and return it
            this.visited.put(node, new Node(node.val, null, null));
            return this.visited.get(node);
        }
    }
    return null;
}

public Node copyRandomList_3(Node head) {

    if (head == null) {
        return null;
    }

    Node oldNode = head;

    // Creating the new head node.
    Node newNode = new Node(oldNode.val);
    this.visited.put(oldNode, newNode);

    // Iterate on the linked list until all nodes are cloned.
    while (oldNode != null) {
        // Get the clones of the nodes referenced by random and next pointers.
        newNode.random = this.getClonedNode(oldNode.random);
        newNode.next = this.getClonedNode(oldNode.next);

        // Move one step ahead in the linked list.
        oldNode = oldNode.next;
        newNode = newNode.next;
    }
    return this.visited.get(head);
}

// java
// LC 817
    // V1
    // IDEA: set, linkedlist (gpt)
    public int numComponents_1(ListNode head, int[] nums) {
        // Convert nums array to a HashSet for O(1) lookups
        Set<Integer> numsSet = new HashSet<>();
        for (int num : nums) {
            numsSet.add(num);
        }

        int count = 0;
        boolean inComponent = false;

        // Traverse the linked list
        while (head != null) {
            if (numsSet.contains(head.val)) {
                // Start a new component if not already in one
                if (!inComponent) {
                    count++;
                    inComponent = true;
                }
            } else {
                // End the current component
                inComponent = false;
            }
            head = head.next;
        }

        return count;
    }

// java
// LC 430 - Flatten a Multilevel Doubly Linked List
// IDEA: IN-PLACE SPLICE — insert the child chain between `cur` and `cur.next`
// time = O(n), space = O(1)   (each chain is tail-scanned exactly once)
public Node flatten(Node head) {
    Node cur = head;
    while (cur != null) {
        if (cur.child != null) {
            Node next  = cur.next;          // save the successor
            Node child = cur.child;
            cur.child = null;               // MUST clear the child pointer

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

            // find the child chain's tail
            Node tail = child;
            while (tail.next != null) tail = tail.next;

            // seam 2: tail <-> next
            tail.next = next;
            if (next != null) next.prev = tail;
        }
        cur = cur.next;                     // walks INTO the spliced child
    }
    return head;
}

# python
# LC 430 - Flatten a Multilevel Doubly Linked List
# IDEA: IN-PLACE SPLICE — insert the child chain between `cur` and `cur.next`
# time = O(n), space = O(1)   (each chain is tail-scanned exactly once)
def flatten(self, head):
    cur = head
    while cur:
        if cur.child:
            nxt   = cur.next                # save the successor
            child = cur.child
            cur.child = None                # MUST clear the child pointer

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

            # find the child chain's tail
            tail = child
            while tail.next:
                tail = tail.next

            # seam 2: tail <-> nxt
            tail.next = nxt
            if nxt:
                nxt.prev = tail
        cur = cur.next                      # walks INTO the spliced child
    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

// java
// LC 369
// V1
// IDEA : LINKED LIST OP (gpt)
/**
*  Step 1) reverse linked list
*  Step 2) plus 1, bring `carry` to next digit if curSum > 9, ... repeat for all nodes
*  Step 3) reverse linked list again
*/
public ListNode plusOne_1(ListNode head) {
if (head == null) return new ListNode(1); // Handle edge case

// Reverse the linked list
head = reverseList(head);

// Add one to the reversed list
ListNode current = head;
int carry = 1; // Start with adding one

while (current != null && carry > 0) {
  int sum = current.val + carry;
  current.val = sum % 10; // Update the current node value
  carry = sum / 10; // Calculate carry for the next node
  if (current.next == null && carry > 0) {
    current.next = new ListNode(carry); // Add a new node for carry
    carry = 0; // No more carry after this
  }
  current = current.next;
}

// Reverse the list back to original order
return reverseList(head);
}

// Utility to reverse a linked list
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;

while (current != null) {
  ListNode next = current.next; // Save the next node
  current.next = prev; // Reverse the link
  prev = current; // Move prev forward
  current = next; // Move current forward
}

return prev;
}

// java
// LC 148 - Sort List
// IDEA: MERGE SORT — split at middle (slow/fast) -> sort halves -> merge
// time = O(n log n), space = O(log n) (recursion stack)
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;

    // 1) split: `slow` stops at the node BEFORE the middle
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode mid = slow.next;
    slow.next = null;                       // cut into two halves

    // 2) sort each half
    ListNode l = sortList(head), r = sortList(mid);

    // 3) merge (LC 21)
    return mergeTwo(l, r);
}

private ListNode mergeTwo(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), cur = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { cur.next = a; a = a.next; }
        else                { cur.next = b; b = b.next; }
        cur = cur.next;
    }
    cur.next = (a != null) ? a : b;         // attach the leftover tail
    return dummy.next;
}

# python
# LC 148 - Sort List
# IDEA: MERGE SORT — split at middle (slow/fast) -> sort halves -> merge
# time = O(n log n), space = O(log n) (recursion stack)
def sortList(self, head):
    if not head or not head.next:
        return head

    # 1) split: `slow` stops at the node BEFORE the middle
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None                        # cut into two halves

    # 2) sort each half
    left, right = self.sortList(head), self.sortList(mid)

    # 3) merge (LC 21)
    return self.merge_two(left, right)

def merge_two(self, a, b):
    dummy = ListNode(0)
    cur = dummy
    while a and b:
        if a.val <= b.val:
            cur.next, a = a, a.next
        else:
            cur.next, b = b, b.next
        cur = cur.next
    cur.next = a if a else b                # attach the leftover tail
    return dummy.next

split:   [4,2]        [1,3]
split:   [4] [2]      [1] [3]
merge:   [2,4]        [1,3]
merge:   [1,2,3,4]

// java
// LC 147 - Insertion Sort List
// 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;           // detach `cur` first
        ListNode p = dummy;
        while (p.next != null && p.next.val < cur.val) p = p.next;
        cur.next = p.next;                  // splice `cur` after `p`
        p.next = cur;
        cur = next;
    }
    return dummy.next;
}

# python
# LC 147 - Insertion Sort List
# time = O(n^2), space = O(1)
def insertionSortList(self, head):
    dummy = ListNode(0)
    cur = head
    while cur:
        nxt = cur.next                      # detach `cur` first
        p = dummy
        while p.next and p.next.val < cur.val:
            p = p.next
        cur.next = p.next                   # splice `cur` after `p`
        p.next = cur
        cur = nxt
    return dummy.next

// java
// LC 1171 - Remove Zero Sum Consecutive Nodes from Linked List
// IDEA: PREFIX SUM + HASHMAP — same prefix twice => the nodes in between sum to 0
// time = O(n), space = O(n)
public ListNode removeZeroSumSublists(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    // pass 1: remember the LAST node achieving each prefix sum
    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);          // overwrite -> keeps the last one
    }

    // pass 2: jump from the FIRST node with prefix p to the LAST node with prefix p
    prefix = 0;
    for (ListNode cur = dummy; cur != null; cur = cur.next) {
        prefix += cur.val;
        cur.next = lastSeen.get(prefix).next;
    }
    return dummy.next;
}

# python
# LC 1171 - Remove Zero Sum Consecutive Nodes from Linked List
# IDEA: PREFIX SUM + HASHMAP — same prefix twice => the nodes in between sum to 0
# time = O(n), space = O(n)
def removeZeroSumSublists(self, head):
    dummy = ListNode(0, head)

    # pass 1: remember the LAST node achieving 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: jump from the FIRST node with prefix p to 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

node    : dummy  1   2   -3   3   1
prefix  :   0    1   3    0   3   4
                 ^        ^        prefix 0 repeats -> drop [1,2,-3]
                     ^        ^    prefix 3 repeats -> drop [3]
result  : 3 -> 1

// java
// LC 1019 - Next Greater Node In Linked List
// IDEA: dump list -> array, then MONOTONIC DECREASING STACK of indices
// 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];                 // default 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;
}

# python
# LC 1019 - Next Greater Node In Linked List
# IDEA: dump list -> array, then MONOTONIC DECREASING STACK of indices
# time = O(n), space = O(n)
def nextLargerNodes(self, head):
    vals, cur = [], head
    while cur:
        vals.append(cur.val)
        cur = cur.next

    res = [0] * len(vals)                   # default 0 = "no greater node"
    stack = []                              # indices, values decreasing
    for i, v in enumerate(vals):
        while stack and vals[stack[-1]] < v:
            res[stack.pop()] = v
        stack.append(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]
leftover 1,4 -> res = [7, 0, 5, 5, 0]