A freight train is a linked list of wagons built from the provided ListNode class (fields val and next); the head is the wagon right behind the locomotive and val is its load in tonnes. The locomotive can pull at most limit tonnes.
Keep the longest front part of the train whose total load is <= limit. Everything behind it is uncoupled and shunted backwards onto a siding, which reverses its order: the wagon that was last in the train becomes the first on the siding.
Write shunt(head, limit) that returns a tuple (train, siding): the head of the kept train and the head of the siding, each None if empty. Reuse the original nodes by relinking them (the tests check node identity), and make sure the kept train's last wagon no longer points at the siding.
train 4 -> 2 -> 5 -> 1 -> 3, limit 7
4 + 2 = 6 fits, adding 5 would be 11
train: 4 -> 2
siding: 3 -> 1 -> 5
train 8 -> 1, limit 5 train: None siding: 1 -> 8
train 1 -> 1, limit 10 train: 1 -> 1 siding: None
Constraints: up to 2 * 10^5 wagons, loads between 0 and 10^6, 0 <= limit <= 10^12, head may be None. Work iteratively (the long test is far deeper than Python's recursion limit), with O(1) extra memory: don't copy the wagons into a Python list.
Show hint
walk from the head adding loads until the next wagon would go over; remember the last kept wagon and cut its next; then reverse the rest with the usual three pointers (prev, cur, nxt).