0% completed
Problem Statement
Given the head of two sorted linked lists, l1
and l2
.
Return a new sorted list created by merging together the nodes of the first two lists.
Examples
-
Example 1:
- Input:
[1, 3, 5] [2, 4, 6]
- Expected Output:
[1, 2, 3, 4, 5, 6]
- Justification: Merging the two sorted linked lists, node by node, results in a single sorted linked list containing all elements from both input lists.
- Input:
-
Example 2:
- Input:
[2, 4, 6] [1, 3, 5]
- Expected Output:
[1, 2, 3, 4, 5, 6]
- Justification: Both lists are in ascending order; merging them node by node in ascending order gives us the sorted linked list with all elements.
- Input:
-
Example 3:
- Input:
[1, 2, 3] [4, 5, 6]
- Expected Output:
[1, 2, 3, 4, 5, 6]
- Justification: As the first list contains all smaller elements, combining them results in a new list with elements from the first list followed by the second one.
- Input:
Constraints:
- The number of nodes in both lists is in the range
[0, 50]
. -100 <= Node.val <= 100
- Both
list1
andlist2
are sorted in non-decreasing order.
Solution
To solve the problem, iteratively compare the nodes of the two given lists and merge them into a new sorted list. Start with a placeholder node as the head of the merged list. Compare the current nodes of both lists; whichever node has the smaller value gets appended to the merged list. Then, move forward in the list that had the smaller element. Repeat this process until one of the lists is fully traversed. At this point, simply append the remaining elements of the other list to the merged list. The placeholder head is then skipped, and the next node is returned as the head of the new, sorted merged list.
-
Initialization:
- Start by initializing two pointers,
l1
andl2
, at the heads of the first and second lists respectively. - Create a dummy node to keep track of the head of the merged list, and a
current
pointer to build the new list.
- Start by initializing two pointers,
-
Node Comparison and Merging:
- Compare the values at
l1
andl2
. Append the node with the smaller value to thecurrent
pointer. - Move the pointer (
l1
orl2
) whose node has been used forward.
- Compare the values at
-
List Traversal:
- Continue this process of comparing, appending, and moving pointers until you reach the end of one of the lists.
- Once one of the lists is exhausted, append the remaining nodes from the other non-empty list to
current
.
-
Final Output:
- After traversing both lists, the
current
pointer will have a sorted merged list attached to it. Return thenext
of the dummy node as the head of the merged list.
- After traversing both lists, the
Algorithm Walkthrough
- Start with the first nodes of the two lists, compare them and attach the smaller one to
current
. - Move forward in the list from which the node was taken.
- Continue this process, comparing nodes and appending the smaller one to
current
. - If one of the lists is exhausted, append the remaining nodes from the other list.
- Return the
next
of the dummy node as the output.
Here is the visual representation of the algorithm:
Code
Here is the code for this algorithm:
Time Complexity:
- O(n + m): The time complexity of merging two sorted linked lists is linear, where
n
andm
are the lengths of the two input lists. In each step, we're deciding which node (from the two lists) with the smaller value should be added next to the merged list. We continue this process until one of the lists is empty, and then append the remaining list. As a result, every node is visited once, which leads to O(n + m) time complexity.
Space Complexity:
- O(1): The space complexity is constant since we are not using any additional data structures that scale with input size. We're only using a few extra variables to keep track of the current node and the head of the merged list. All other nodes are part of the input or output, and do not count towards the space complexity. The input lists are being used to construct the output list in-place, so the algorithm is very space-efficient.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible