Back to Linked List
Easy
Merge Two Sorted Lists
You are given the heads of two sorted linked lists `list1` and `list2`. Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.
Examples
Input:list1 = [1,2,4], list2 = [1,3,4]
Output:[1,1,2,3,4,4]
Input:list1 = [], list2 = []
Output:[]
Constraints
The number of nodes in both lists is in the range [0, 50].-100 <= Node.val <= 100Both list1 and list2 are sorted in non-decreasing order.
Approach
Create a dummy head node to simplify edge cases. Use a `tail` pointer starting at the dummy node. While both lists are not null, compare their values. Attach the smaller node to `tail.next`, and advance the pointer of the list from which the node was taken. Also advance `tail`. Once one list runs out, attach the remaining part of the other list directly to `tail.next`. Return `dummy.next`.
Complexity Analysis
Time Complexity
O(n + m)
Space Complexity
O(1)
This uses constant space since we are just modifying pointers of existing nodes.
Solution.java
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(0); ListNode tail = dummy; while (list1 != null && list2 != null) { if (list1.val < list2.val) { tail.next = list1; list1 = list1.next; } else { tail.next = list2; list2 = list2.next; } tail = tail.next; } // Attach the remaining nodes if (list1 != null) { tail.next = list1; } else if (list2 != null) { tail.next = list2; } return dummy.next; }}