-
Notifications
You must be signed in to change notification settings - Fork 2
/
sorting_linked_list.py
85 lines (77 loc) · 2.29 KB
/
sorting_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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
# Author: BHARATHI KANNAN N - Github: https://github.com/bharathikannann, linkedin: https://linkedin.com/in/bharathikannann
#
# Sorting in Linked lists
# Merge sort algorithm
class Node():
def __init__(self, data, next=None):
self.data=data
self.next=next
class LinkedList(object):
def __init__(self):
self.head = None
def insertAtFirst(self, data):
newNode = Node(data)
newNode.next = self.head
self.head = newNode
def show(self):
if(self.head == None):
print("No element present in the list")
return
temp = self.head
while(temp):
print(temp.data, end='->')
temp=temp.next
print("None")
# ------------------------------------------------------------------------------------------
# Merge sort linked list
def sort(self):
self.head = self.mergeSort(self.head)
# Divide the linked list
# To find middle element use slow and fast node
# Then split until one node or none is present
# Then merge
def mergeSort(self, node):
if(node == None or node.next == None):
return node
slow = node
fast = node
temp = node
while(fast != None and fast.next != None):
temp = slow
slow = slow.next
fast = fast.next.next
temp.next = None
left = self.mergeSort(node)
right = self.mergeSort(slow)
return self.merge(left, right)
# Merge the lists
def merge(self, a, b):
result = None
if(a == None):
return b
if(b == None):
return a
# If data of first node is small then append the merge list of b with remaining of a
if(a.data <= b.data):
result = a
result.next = self.merge(a.next, b)
else:
result = b
result.next = self.merge(a, b.next)
# Return the sorted merged list
return result
if __name__ == "__main__":
ll = LinkedList()
ll.insertAtFirst(10)
ll.insertAtFirst(20)
ll.insertAtFirst(30)
ll.insertAtFirst(40)
ll.insertAtFirst(50)
ll.show()
ll.sort()
ll.show()
'''
Output
50->40->30->20->10->None
10->20->30->40->50->None
'''