-
Notifications
You must be signed in to change notification settings - Fork 0
/
86. Partition List.py
35 lines (35 loc) · 1.56 KB
/
86. Partition List.py
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
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
# No idea, need to read solution
# before and after are the two pointers used to create two list
# before_head and after_head are used to save the heads of the two lists.
# All of these are initialized with the dummy nodes created.
before = before_head = ListNode(0)
after = after_head = ListNode(0)
while head:
# If the original list node is lesser than the given x,
# assign it to the before list.
if head.val < x:
before.next = head
before = before.next
else:
# If the original list node is greater or equal to the given x,
# assign it to the after list.
after.next = head
after = after.next
head = head.next
# Last node of "after" list would also be ending node of the reformed list
after.next = None
# Once all the nodes are correctly assigned to the two lists,
# combine them to form a single list which would be returned.
before.next = after_head.next
return before_head.next