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.
Idea #1 (Time: N, Memory: N)
- Compare value of each list head node.
- Bigger one will be added in res list.
- If one of head node doesn't exit, add left one to res list.
Idea #2 (Time: N log N, Memory: N)
- Parse all linked list to list
- Concatenate lists
- Sort using quick sort algorithm
- Convert List to Linked List
Test Cases
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]
Code
# 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]:
node = ListNode(val=0)
res = node
tmp = None
while list1 and list2:
# Compare value of each list head node
if list1.val <= list2.val:
# Bigger one will be added in res list.
tmp = list1
list1 = list1.next
else:
tmp = list2
list2 = list2.next
node.next = ListNode(tmp.val)
node = node.next
# If one of head doesn't exit, add left one to res list.
if list1 and not list2:
tmp = list1
elif not list1 and list2:
tmp = list2
else: return None
while tmp:
node.next = ListNode(tmp.val)
node = node.next
tmp = tmp.next
return res.next
Top comments (0)