Question:
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into 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.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
Answer:
The problem requires merging two sorted linked lists into one sorted linked list. The basic intuition is to compare the values of nodes from the two lists and link them in sorted order.
Approach:
- Initialize a dummy node as the starting point of the merged list.
- Initialize a pointer 'current' to traverse the merged list.
- Iterate over the two input lists simultaneously.
- At each iteration, compare the values of the current nodes of the input lists.
- Append the smaller node to the merged list and move the corresponding pointer forward.
- Continue this process until one of the input lists becomes empty.
- Append the remaining nodes of the non-empty list to the merged list.
- Return the head of the merged list, excluding the dummy node.
Time complexity:
The time complexity of the algorithm is O(n), where n is the total number of nodes in the merged list. This is because we iterate through each node of the input lists exactly once.
Space complexity:
The space complexity of the algorithm is O(1) because we only use a constant amount of extra space regardless of the size of the input lists.
Code:
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next
class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: dummy = ListNode() current = dummy while l1 and l2: if l1.val < l2.val: current.next = l1 l1 = l1.next else: current.next = l2 l2 = l2.next current = current.next current.next = l1 or l2 return dummy.next
.png)
.png)
.png)
0 Comments