動機
直接往後塞
Problem
Given the head
of 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.
Example 1:
Input: head = [1,4,3,2,5,2], x = 3Output: [1,2,2,4,3,5]
Example 2:
Input: head = [2,1], x = 2Output: [1,2]
Constraints:
- The number of nodes in the list is in the range
[0, 200]
. -100 <= Node.val <= 100
-200 <= x <= 200
Sol
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
ret = head
end = head
prev = None
acc = 1
if not head:
return head
while end.next:
end = end.next
acc += 1
for i in range(0,acc):
if head.val >= x:
end.next = head
head = head.next
end = end.next
end.next = None
if prev:
prev.next = head
else:
ret = head
else:
prev = head
head = head.next
return ret