EasyTopicsCompaniesYou are given the heads of two sorted linked lists list1 and list2.Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.Return the head of the merged linked list. 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] Constraints:The number of nodes in both lists is in the range [0, 50].-100 <= Node.val <= 100Both list1 and list2 are sorted in non-decreasing order.

Here is a step-by-step solution in Python:

1. First, we need to handle the edge cases where one or both of the lists are empty. If both lists are empty, we return an empty list. If one of the lists is empty, we return the other list.

if not list1:
    return list2
if not list2:
    return list1

2. We initialize a new linked list to store the merged result. We also need a pointer (let's call it current) to keep track of the last node we've added to this new list.

merged = ListNode(0)  # dummy node
current = merged

3. Then we start a loop that continues until we've gone through every node in both lists. In each iteration of the loop, we compare the values of the current nodes of list1 and list2, and add the smaller one to merged. We then move the pointer of the list from which we've taken a node to the next node.

while list1 and list2:
    if list1.val < list2.val:
        current.next = list1
        list1 = list1.next
    else:
        current.next = list2
        list2 = list2.next
    current = current.next

4. After the loop, it's possible that one list still has some nodes while the other doesn't. We add the remaining nodes to merged.

if list1:
    current.next = list1
else:
    current.next = list2

5. Finally, we return the next of the dummy node, which is the head of the merged list.

return merged.next

Here is the complete code:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def mergeTwoLists(list1, list2):
    if not list1:
        return list2
    if not list2:
        return list1

    merged = ListNode(0)  # dummy node
    current = merged

    while list1 and list2:
        if list1.val < list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next

    if list1:
        current.next = list1
    else:
        current.next = list2

    return merged.next