21 Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example 1:

``````1 -> 2 -> 4
1 -> 3 -> 4
------------
1 -> 1 -> 2 -> 3 -> 4 -> 4

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
``````

Example 2:

``````Input: l1 = [], l2 = []
Output: []
``````

Example 3:

``````Input: l1 = [], l2 = [0]
Output: [0]
``````

Constraints:

• The number of nodes in both lists is in the range `[0, 50]`.
• `-100 <= Node.val <= 100`
• Both `l1` and `l2` are sorted in non-decreasing order.
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 `````` ``````# 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, l1: Optional[ListNode], l2: Optional[ListNode] ) -> Optional[ListNode]: if l1 is None: return l2 if l2 is None: return l1 if l1.val < l2.val: l1.next = self.mergeTwoLists(l1.next, l2) return l1 l2.next = self.mergeTwoLists(l1, l2.next) return l2``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 `````` ``````func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { if l1 == nil { return l2 } if l2 == nil { return l1 } result := ListNode{} if l1.Val < l2.Val { result.Val = l1.Val result.Next = mergeTwoLists(l1.Next, l2) } else { result.Val = l2.Val result.Next = mergeTwoLists(l1, l2.Next) } return &result }``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 `````` ``````public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } if (l2 == null) { return l1; } ListNode mergeHead; if(l1.val < l2.val){ mergeHead = l1; mergeHead.next = mergeTwoLists(l1.next, l2); } else { mergeHead = l2; mergeHead.next = mergeTwoLists(l1, l2.next); } return mergeHead; }``````