easyLinked ListPattern: Merge
Merge Two Sorted Linked Lists Solution
Problem Statement
You are given the heads of two sorted linked lists, `list1` and `list2`. Merge the two lists into one sorted linked list and return the head of the merged list. The list should be made by splicing together the nodes of the first two lists. Ensure the resulting list remains sorted.
Examples
Example 1:
Input:list1 = [1,2,4], list2 = [1,3,4]
Output:[1,1,2,3,4,4]
Explanation: The nodes of list1 and list2 are merged into a single sorted list: [1,1,2,3,4,4].
Example 2:
Input:list1 = [], list2 = []
Output:[]
Explanation: If both lists are empty, the merged list is also empty.
Example 3:
Input:list1 = [], list2 = [0]
Output:[0]
Explanation: If one list is empty, the merged list is the other 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.
Time: O(N + M) Space: O(1)
Iterate through both sorted linked lists simultaneously using two pointers. Maintain a pointer to the current node in the merged list. At each step, compare the values of the current nodes in `list1` and `list2`, append the node with the smaller value to the merged list, and advance the corresponding pointer. A dummy head node can simplify the initial setup. Once one list is exhausted, append the remainder of the other list.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy_head = ListNode(0)
current = dummy_head
while list1 is not None and list2 is not None:
if list1.val <= list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
# Append remaining nodes
if list1 is not None:
current.next = list1
elif list2 is not None:
current.next = list2
return dummy_head.next