Sort List Visualizer & Step-by-Step Algorithm Solution

Sort a linked list in O(n log n) time using top-down Merge Sort with divide-and-conquer recursion.

Category: linked-list | Difficulty: Medium

Tags: Linked List, Merge Sort, Divide and Conquer, Recursion

Sort List

head
4
2
1
3
∅
100%
state
headNode(4)
Sort
1/64
Explanation

Call sortList with head 4.

Source Code
1function sortList(head) {
2 if (!head || !head.next) return head;
3 let slow = head, fast = head;
4 while (fast.next && fast.next.next) {
5 slow = slow.next;
6 fast = fast.next.next;
7 }
8 const mid = slow.next;
9 slow.next = null;
10 const left = sortList(head);
11 const right = sortList(mid);
12 return merge(left, right);
13}
14
15function merge(l1, l2) {
16 const dummy = new ListNode(-1);
17 let curr = dummy;
18 while (l1 && l2) {
19 if (l1.val > l2.val) {
20 curr.next = l2; l2 = l2.next;
21 } else {
22 curr.next = l1; l1 = l1.next;
23 }
24 curr = curr.next;
25 }
26 curr.next = l1 || l2;
27 return dummy.next;
28}