-
Notifications
You must be signed in to change notification settings - Fork 232
/
rearrange-linked-list.py
61 lines (55 loc) · 1.43 KB
/
rearrange-linked-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
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
# REARRANGE LINKED LIST
# This is the class of the input linked list.
class LinkedList:
def __init__(self, value):
self.value = value
self.next = None
# O(N) time and O(1) space
def rearrangeLinkedList(head, k):
# Write your code here.
headOfSmall = None
pointerSmall = None
headOfLarge = None
pointerLarge = None
current = head
nodeWithValueK = None
pointerNodeWithValueK = None
while current is not None:
if current.value < k:
if headOfSmall is None:
headOfSmall = current
pointerSmall = current
else:
pointerSmall.next = current
pointerSmall = pointerSmall.next
elif current.value == k:
if nodeWithValueK is None:
nodeWithValueK = current
pointerNodeWithValueK = current
else:
pointerNodeWithValueK.next = current
pointerNodeWithValueK = pointerNodeWithValueK.next
else:
if headOfLarge is None:
headOfLarge = current
pointerLarge = current
else:
pointerLarge.next = current
pointerLarge = pointerLarge.next
current = current.next
if pointerLarge is not None:
pointerLarge.next = None
if nodeWithValueK is None:
if pointerSmall is None:
return headOfLarge
else:
pointerSmall.next = headOfLarge
return headOfSmall
else:
if pointerSmall is None:
pointerNodeWithValueK.next = headOfLarge
return nodeWithValueK
else:
pointerSmall.next = nodeWithValueK
pointerNodeWithValueK.next = headOfLarge
return headOfSmall