Merge Two Sorted Lists
easy●Linked Lists
You are given the heads of two sorted linked lists `list1` and `list2`.
Merge the two lists into one sorted linked list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
### How it works (Iterative Two-Pointer approach): Because both lists are already sorted, we can build the merged list efficiently by repeatedly comparing the smallest available elements from both lists.
1. **Dummy Head**: Create a `dummy` node. This helps us easily return the start of the merged list later. Create a `tail` pointer that starts at the dummy node. 2. Initialize two pointers, `curr1` and `curr2`, at the heads of `list1` and `list2` respectively. 3. Keep looping as long as both pointers are not `null`: - Compare `curr1.val` and `curr2.val`. - Take the smaller node and append it to the `tail` of our merged list. - Move the pointer of the list we just took a node from, and move the `tail` pointer forward. 4. Once one list runs out, append the entirety of the remaining list to `tail.next`. 5. Return `dummy.next`, which is the true head of the merged list.
Merge the two lists into one sorted linked list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
### How it works (Iterative Two-Pointer approach): Because both lists are already sorted, we can build the merged list efficiently by repeatedly comparing the smallest available elements from both lists.
1. **Dummy Head**: Create a `dummy` node. This helps us easily return the start of the merged list later. Create a `tail` pointer that starts at the dummy node. 2. Initialize two pointers, `curr1` and `curr2`, at the heads of `list1` and `list2` respectively. 3. Keep looping as long as both pointers are not `null`: - Compare `curr1.val` and `curr2.val`. - Take the smaller node and append it to the `tail` of our merged list. - Move the pointer of the list we just took a node from, and move the `tail` pointer forward. 4. Once one list runs out, append the entirety of the remaining list to `tail.next`. 5. Return `dummy.next`, which is the true head of the merged list.
Constraints
- The number of nodes in both lists is in the range [0, 50].
- -100 <= Node.val <= 100
- Both list1 and list2 are sorted in non-decreasing order.
TimeO(O(n + m))
SpaceO(O(1))
Ready to startStep 0 / 0
TypeScript