Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a singly linked list of integers node, sort the nodes by their values in ascending order.
Constraints
n ≤ 100,000 where n is the number of nodes in node
Example 1
Input
Visualize
node = [14, 13, 10]
Output
Visualize
[10, 13, 14]
Merge Sorting a Linked List (Divide and Conquer Technique)
Given a Linked List, we can find the middle of the linked list using fast and slow pointer, disconnect the linked list at the middle point to make two sub linked lists. Recursively sort them and merge two linked list.
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 | # class LLNode: # def __init__(self, val, next=None): # self.val = val # self.next = next class Solution: def sortLinkedList(self, node): def mid(head): if head is None or head.next is None: return head fast, slow = head, head prev = None while fast and fast.next: fast = fast.next.next prev = slow slow = slow.next prev.next = None return slow def merge(a, b): dummy = LLNode(-1) p = dummy while a and b: if a.val < b.val: p.next = a a = a.next else: p.next = b b = b.next p = p.next if a: p.next = a if b: p.next = b return dummy.next if node is None or node.next is None: return node # Recursively sort the left linked list a = self.sortLinkedList(mid(node)) # Recursively sort the right linked list b = self.sortLinkedList(node) return merge(a, b) |
# class LLNode: # def __init__(self, val, next=None): # self.val = val # self.next = next class Solution: def sortLinkedList(self, node): def mid(head): if head is None or head.next is None: return head fast, slow = head, head prev = None while fast and fast.next: fast = fast.next.next prev = slow slow = slow.next prev.next = None return slow def merge(a, b): dummy = LLNode(-1) p = dummy while a and b: if a.val < b.val: p.next = a a = a.next else: p.next = b b = b.next p = p.next if a: p.next = a if b: p.next = b return dummy.next if node is None or node.next is None: return node # Recursively sort the left linked list a = self.sortLinkedList(mid(node)) # Recursively sort the right linked list b = self.sortLinkedList(node) return merge(a, b)
Merging two sorted linked lists is quite the same as merging two sorted lists. It requires O(N+M) time. Overall, the complexity of sorting a linked list is O(NLogN).
Sort List by Additional Space
However, we can copy the linked list to a list, sort the list in O(NLogN) and iterate the linked list to overwrite the values:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | # class LLNode: # def __init__(self, val, next=None): # self.val = val # self.next = next class Solution: def sortLinkedList(self, node): values = [] head = node while node: values.append(node.val) node = node.next values.sort() values = collections.deque(values) node = head while node: node.val = values.popleft() node = node.next return head |
# class LLNode: # def __init__(self, val, next=None): # self.val = val # self.next = next class Solution: def sortLinkedList(self, node): values = [] head = node while node: values.append(node.val) node = node.next values.sort() values = collections.deque(values) node = head while node: node.val = values.popleft() node = node.next return head
See also: Teaching Kids Programming – MergeSort Simply Explained
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Binary Search Algorithm to Find Next Node on Its Right in a Binary Tree
Next Post: Teaching Kids Programming - Using Binary Search to Find K-th Largest Number in Array