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)