Search for a command to run...
Sort a linked list in O(n log n) time and O(log n) space using Merge Sort
Initial Unsorted List
Sorting list: 3 → 2 → 5 → 4 → 1 using Merge Sort.
Merge Sort
1class Solution {2 mergeTwoSortedLinkedLists(list1, list2) {3 let dummyNode = new ListNode(-1);4 let temp = dummyNode;5 6 while (list1 !== null && list2 !== null) {7 if (list1.val <= list2.val) {8 temp.next = list1;9 list1 = list1.next;10 } else {11 temp.next = list2;12 list2 = list2.next;13 }14 temp = temp.next; 15 }16 17 if (list1 !== null) {18 temp.next = list1;19 } else {20 temp.next = list2;21 }22 return dummyNode.next;23 }24 25 findMiddle(head) {26 if (head === null || head.next === null) {27 return head;28 }29 30 let slow = head;31 let fast = head.next;32 33 while (fast !== null && fast.next !== null) {34 slow = slow.next;35 fast = fast.next.next;36 }37 return slow;38 }39 40 sortList(head) {41 if (head === null || head.next === null) {42 return head;43 }44 45 let middle = this.findMiddle(head);46 47 let right = middle.next;48 middle.next = null;49 let left = head;50 51 left = this.sortList(left);52 right = this.sortList(right);53 54 return this.mergeTwoSortedLinkedLists(left, right);55 }56}