Merge Two Sorted Linked List

Problem Statement: Merge Two Sorted Linked List

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists in a 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: list1 = [1,2,4], list2 = [1,3,4]

Output: [1,1,2,3,4,4]

We have presented two approaches to solve the problem:

Approach 1: Using Extra Space

The goal of this problem is to create a merged list that contains elements from both L1 and L2 in a sorted manner. The easiest way to go about this problem would be to store the elements of both L1 and L2 in an array, then sort the array, then reconstruct a new linkedlist maintaining the order of the new array. The runtime complexity of our algorithm would be O(N + NlogN + N), where N is the number of elements from L1 + L2.

Unfortunately, this is rather inefficient because we do not make use of the advantages of a linkedlist. LinkedLists are special due to their pointers, which make them very flexible and we can move them around in the array in constant time if we have the references.

How can we make a more optimized solution reflecting on the above points?

let's create a algorithm.

1. Initialize dummy node

2. While both pointers of L1 and L2 are not None

3. If L1's value is smaller, choose L1 & iterate L1's pointer to next

4. If L2's value is smaller, choose L2 & iterate L2's pointer to next

5. Iterate Dummy Pointer to next and return Dummy's next

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode dummy(INT_MIN);
        ListNode *tail = &dummy;
        
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }

        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

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

def display(node):
    while node:
        print(node.val, end = ' -> ')
        node = node.next
    print('X')

def merge_lists(node1, node2):
    if not node1:
        return node2
    if not node2:
        return node1
    if node1.val <= node2.val:
        temp = node1
        node1 = node1.next
    else:
        temp = node2
        node2 = node2.next
    head = temp
    while node1 and node2:
        if node1.val <= node2.val:
            temp.next = node1
            temp = temp.next
            node1 = node1.next
        else:
            temp.next = node2
            temp = temp.next
            node2 = node2.next
    if not node1:
        temp.next = node2
    else:
        temp.next = node1
    return head

if __name__=='__main__':
    node1 = Node(2)
    node1.next = Node(4)
    node1.next.next = Node(5)
    node1.next.next.next = Node(8)
    
    node2 = Node(1)
    node2.next = Node(3)
    node2.next.next = Node(6)
    node2.next.next.next = Node(7)
    
    node = merge_lists(node1, node2)
    display(node)

Time Complexity: We are still traversing both lists entirely in the worst-case scenario. So, it remains the same as O(N+M) where N is the number of nodes in list 1 and M is the number of nodes in list 2.

Space Complexity: O(1)