Merge Two Sorted Lists Visualizer & Step-by-Step Algorithm Solution

Merge two sorted linked lists into a single sorted list by splicing together node pointers in O(n + m) time.

Category: linked-list | Difficulty: Easy

Tags: Linked List, Two Pointers, Simulation

Merge Two Sorted Lists

list1
1
2
4
∅
list2
1
3
4
∅
100%
state
t1undefined
t2undefined
tailundefined
Initialization
1/33
Explanation

Starting mergeTwoLists with List 1 (3 nodes) and List 2 (3 nodes).

Source Code
1function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
2 let dummy = new ListNode(-1);
3 let tail = dummy;
4
5 let t1 = list1;
6 let t2 = list2;
7
8 while (t1 && t2) {
9 if (t1.val <= t2.val) {
10 tail.next = t1;
11 t1 = t1.next;
12 } else {
13 tail.next = t2;
14 t2 = t2.next;
15 }
16 tail = tail.next;
17 }
18
19 if (t1 !== null) tail.next = t1;
20 else tail.next = t2;
21
22 return dummy.next;
23}