How To Merge Two Sorted Lists

Task description:

You 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 <= 100
• Both list1 and list2 are sorted in non-decreasing order.

Reasoning:

LinkedList is another widely used data structure. It could be singly linked or doubly linked.

For this particular task we can assume that we work with singly linked version. As you can see every linked list consists of small pieces called Links or Node.

https://gist.github.com/RakhmedovRS/341071fbc066bcf4a3b2c228e51fc7ff

As you can see from the pictures and code above every LinkedNode stores a link to the next LinkedNode. The first LinkedNode is usually called the head whereas the last one is called the tail. With a singly linked version we can only traverse from the head to the tail of the list and there’s no way to return to the previous node once we stepped forward. The doubly linked version allows us to traverse in both directions because every ListNode stores pointers to the next and previous ListNodes.

Solution:

This time I provide the full code for the solution and we’ll discuss it

https://gist.github.com/RakhmedovRS/9d7bff26fae314a46d13420028842992

The first thing we do is to create a dummy node for storing links to the future head of the merged linked list, as I said previous every LinkedList has a head.

We also need a current node for storing the link of the current node, so we can use it to attach next node to it

We iterate through both lists till pointers to next nodes are not null. On every such step, we’re looking for a node with minimal value stored in it. We move the pointer to the next for LinkedList which has a current node with minimal value. Eventually one of the pointers of both is null.

The last thing we need to do is to attach the rest of LinkedList which still has some values to our current pointer and return a head of the newly created LinkedList.

The solution above has linear time complexity and doesn’t use additional memory(In terms of big O notation additional pointers can be omitted)

See you in the next article✌️✌️✌️✌️✌️✌️✌️