86. Partition List [Python]
Related Topic
Linked-List. Two-Pointers.
Description
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Sample I/O
Example 1
Methodology
Solution 1
We need to set a prev pointer to indicate the last node which less than target. We iterate the linked list until we find the current node is greater or equal than target and next node is less than target then we need to let prev nodes next pointer point to the currents next node and update prev, we also need to let current nodes next pointer point to its next next node. Since there may be consective nodes that less than target, we need to keep tracking [do not updata head] until we find a node that greater or equal to target then we update head.
This may be hard to think, it would be easier if you draw on paper, here is an edge case 1->2->3->2->1 target is 3.
Solution 2
We can also create two linked lists l1, l2, l1 for value less than target and l2 for value greater or equal than target. After that, we just append the l2 to l1 and return the new linked list.