Slot a new node into place
Insert a value into a sorted list by walking to the node before its place and linking the new node in. About 13 minutes.
Stand before the spot
To add a value to a sorted chain, find the first box that is not smaller than the value. The new box belongs just before it. To connect it, you need the box before that spot, so stand there and look one box ahead.
Walk while the next box is smaller than the value. When the next box is missing or not smaller, stop: the new box goes right after where you are standing.
dummy = ListNode(0, head)
cur = dummy
while cur.next and cur.next.val < value:
cur = cur.nextStand on box 1. The next box, 3, is smaller than 5, so move on.
Two changes, in the right order
The new box must point at the box that follows the spot, which is cur.next. Then cur must point at the new box. Always make the new box's pointer first. If you changed cur's pointer first, the only link to the rest of the chain would be overwritten.
Writing the new node with its next already set, ListNode(value, cur.next), does the first change in the same breath.
cur.next = ListNode(value, cur.next) return dummy.next
What happens if you point box 3 at the new box before pointing the new box at box 7?
- AThe link from box 3 to box 7 is overwritten, and the rest of the list is lost
- BNothing, the order doesn't matter
- CThe value is inserted twice
Show the answer
The link from box 3 to box 7 is overwritten, and the rest of the list is lost. Box 3's pointer was the only way to reach box 7, so changing it first loses the rest.
Insert in order
Given the head of a singly linked list sorted from smallest to largest and a value, insert a new node with that value so the list stays sorted, and return the head. For equal values, either position gives the same list.
head = [1, 3, 7, 9], value = 5 → [1, 3, 5, 7, 9]
0 ≤ number of nodes ≤ 5,000 · -1,000,000 ≤ node.val, value ≤ 1,000,000 · sorted