Merging & splitting lists

Merging takes two sorted lists and produces one sorted list by relinking the existing nodes: compare the two heads, attach the smaller to the result, advance in that list, repeat, and attach whatever remains at the end. No new nodes are created.

Splitting cuts a list into parts: at the middle (with fast and slow pointers), by a condition (odd and even positions, values below and above x), or into k roughly equal parts. Merge sort on a linked list is split plus merge applied recursively, and merging k sorted lists uses a min-heap or pairwise merging.

1. 1Merge two: create a dummy node and a tail pointer at it. While both lists have nodes, attach the smaller head to tail.next, advance that list and advance tail.
2. 2When one list is empty, attach the other list in one step: tail.next = a or b. The remaining nodes are already sorted.
3. 3Return dummy.next. Time O(n + m), extra space O(1).
4. 4Split at the middle: run slow and fast pointers (start fast at head.next so slow ends at the end of the first half), then set second = slow.next and slow.next = None to cut the link.
5. 5Merge sort: if the list has 0 or 1 nodes return it; otherwise split, sort both halves recursively and merge them. Time O(n log n), recursion depth O(log n).
6. 6Merge k lists: push each list's head into a min-heap keyed by value; repeatedly pop the smallest, attach it, and push its next node. With N total nodes this is O(N log k).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_two(a, b):
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val:                # <= keeps equal values stable
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b                    # attach whatever is left
    return dummy.next

def sort_list(head):
    """Merge sort a linked list: O(n log n) time, no array copy."""
    if not head or not head.next:
        return head
    slow, fast = head, head.next          # slow stops at the end of the first half
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    second, slow.next = slow.next, None   # split into two lists
    return merge_two(sort_list(head), sort_list(second))

merge_two relinks existing nodes behind a dummy node and attaches the leftover list in one step; using <= keeps the merge stable. sort_list starts fast at head.next so that a two-node list splits into one and one, avoiding infinite recursion. merge_two is O(n + m) time and O(1) space; sort_list is O(n log n) time with O(log n) recursion depth.

Cost: Merge two: O(n + m) time, O(1) space. Merge sort: O(n log n) time, O(log n) stack (O(1) bottom-up). Merge k: O(N log k) time, O(k) heap.