Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Input: l1 = [], l2 = []
Output: []
Input: l1 = [], l2 = [0]
Output: [0]
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.
Solutions (Click to expand)
Create a sentinel or dummy node to that will point to the beginning of our new linked list. Iterate through both linked lists at the same time using two different pointers comparing the value of the currently referenced nodes. Taking the smallest of the two nodes, link the node to the current node pointer of the new linked list. Continue this until one pointer reaches the end of the their list. Link the remaining part of the longer list to the end of the new list as it is already sorted. Return the new list by referencing the next node of the dummy node