forked from gavinfish/leetcode-share
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path086 Partition List.py
More file actions
63 lines (54 loc) · 1.65 KB
/
086 Partition List.py
File metadata and controls
63 lines (54 loc) · 1.65 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
'''
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.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
'''
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
def to_list(self):
return [self.val] + self.next.to_list() if self.next else [self.val]
class Solution(object):
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
dummy = ListNode(-1)
dummy.next = head
small_dummy = ListNode(-1)
large_dummy = ListNode(-1)
prev = dummy
small_prev = small_dummy
large_prev = large_dummy
while prev.next:
curr = prev.next
if curr.val < x:
small_prev.next = curr
small_prev = small_prev.next
else:
large_prev.next = curr
large_prev = large_prev.next
prev = prev.next
large_prev.next = None
small_prev.next = large_dummy.next
return small_dummy.next
if __name__ == "__main__":
n1 = ListNode(1)
n2 = ListNode(4)
n3 = ListNode(3)
n4 = ListNode(2)
n5 = ListNode(5)
n6 = ListNode(2)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
n5.next = n6
r = Solution().partition(n1, 3)
assert r.to_list() == [1, 2, 2, 4, 3, 5]