Merging, splitting and partitioning lists

brute/brute_force.py

"""The brute force for putting express orders first: swap neighbouring nodes, as bubble sort would.

Whenever a standard order is followed directly by an express order, swap the two nodes (not their values), and
repeat until a pass makes no swap. Swapping only neighbours that are out of place keeps each group's order, and it
needs O(1) memory, but an express order at the end must travel past every standard order before it.
"""
from lists import ListNode, from_list, show


def express_first_by_swaps(head, limit):
    """Return (new head, pairs of neighbours looked at)."""
    dummy = ListNode(None, head)
    looked, changed = 0, True
    while changed:
        changed = False
        prev = dummy
        while prev.next is not None and prev.next.next is not None:
            a, b = prev.next, prev.next.next
            looked += 1
            if a.val >= limit and b.val < limit:  # standard, then express: swap the two nodes
                a.next, b.next, prev.next = b.next, a, b
                changed = True
            prev = prev.next
    return dummy.next, looked


for times in ([45, 20, 90, 15, 60, 30], [50, 70], [40, 25]):
    head, looked = express_first_by_swaps(from_list(times), 40)
    print(f"{times} with limit 40: {show(head)}")

for n in (500, 1_000, 2_000):  # the worst case: every standard order first, then every express order
    kept, looked = express_first_by_swaps(from_list([90] * (n // 2) + [10] * (n // 2)), 40)
    print(f"n = {n:>5,}, express orders last: {looked:>9,} pairs looked at")
n = 100_000
work = (n // 2 + 1) * (n - 1)
print(f"n = {n:,}: about {work:,} pairs, {work / 1e7 / 60:.0f} minutes at 10^7 a second")

[45, 20, 90, 15, 60, 30] with limit 40: 20 -> 15 -> 30 -> 45 -> 90 -> 60 -> None
[50, 70] with limit 40: 50 -> 70 -> None
[40, 25] with limit 40: 25 -> 40 -> None
n =   500, express orders last:   125,249 pairs looked at
n = 1,000, express orders last:   500,499 pairs looked at
n = 2,000, express orders last: 2,000,999 pairs looked at
n = 100,000: about 5,000,049,999 pairs, 8 minutes at 10^7 a second

brute/lists.py

"""Test helpers for singly linked lists: build one from a Python list, read it back, and print it."""


class ListNode:
    """One node: a value and a reference to the next node (None after the last node)."""

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


def from_list(values):
    """Build a linked list holding `values` in order and return its head (None for no values)."""
    dummy = ListNode(None)
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next


def to_list(head):
    """The values from `head` to the end; raises ValueError if the list loops back on itself."""
    values, seen = [], set()
    node = head
    while node is not None:
        if id(node) in seen:
            raise ValueError(f"cycle: after {len(values)} nodes the list returns to a node already seen")
        seen.add(id(node))
        values.append(node.val)
        node = node.next
    return values


def show(head):
    """The list as one line of text, such as 4 -> 9 -> 15 -> None."""
    return " -> ".join([*map(str, to_list(head)), "None"])