-
Notifications
You must be signed in to change notification settings - Fork 35
/
linked-list-split.py
63 lines (57 loc) · 1.38 KB
/
linked-list-split.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
62
63
'''
Question:
Split a linked list into two list with odd and even values.
Retain the order of value and solve with no additional space.
'''
class LinkedList:
def __init__(self,data):
self.data = data
self.next = None
def insert(self,node):
current = self
while(current.next is not None):
current = current.next
current.next = node
def PrintLinkedList(list):
while list is not None:
if list.next is not None:
print(list.data,end=" -> ")
else:
print(list.data,end="\n")
list = list.next
def splitLL(node):
oddHead = None
evenHead = None
odd = None
even = None
while node:
#IMPORTANT: get next
tmp = node.next
if node.data%2 == 0: #even
if evenHead is None:
evenHead = node
even = node
else:
even.next = node
even = node
else: #odd
if oddHead is None:
oddHead = node
odd = node
else:
odd.next = node
odd = node
#IMPORTANT: end each node
node.next = None
#IMPORTANT: next node
node = tmp
return oddHead,evenHead
#create linked list
head = LinkedList(1)
for i in range(2,10):
tmp = LinkedList(i)
head.insert(tmp)
PrintLinkedList(head)
odd,even = splitLL(head)
PrintLinkedList(odd)
PrintLinkedList(even)