How To Merge Two Sorted Lists by@rakhmedovrs

How To Merge Two Sorted Lists

August 1st 2022 7,909 reads
Read on Terminal Reader
Open TLDR
react to story with heart
react to story with light
react to story with boat
react to story with money
The list should be made by splicing together the nodes of the first two lists. It could be singly linked or doubly linked. The number of nodes in both lists is in the range `[0, 50]`-100 <= 100` The first Linked node is usually called the head whereas the last one is called the tail. The solution has a solution and we’ll discuss it in terms of big O notation. We’re looking for a node with minimal value stored in it. We move the pointer to the next for LinkedList which has a head. We also need a current node for storing the link of the current node.
image
Ruslan Rakhmedov HackerNoon profile picture

Ruslan Rakhmedov

Software Engineer, Stripe

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:

image

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.

Singly linked list

Singly linked list


Doubly linked list

Doubly linked list


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.



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

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)

image

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

react to story with heart
react to story with light
react to story with boat
react to story with money
L O A D I N G
. . . comments & more!