Redirecting to
NADOS


  Prev   Next

Merge Two Sorted Linked List







Code never lies; comments sometimes do.
~Ron Jeffries

Merge Two Sorted Linked List

Hey coder. We are going to start with the question "Merge 2 sorted Linked Lists" in this article.

We suggest you go through the problem statement and its question video if you haven't already.

Important Links :Problem link, Question Video, Solution Video

Problem Discussion :

We are required to write a function that is static and is passed two lists which are sorted. The function is expected to return a new sorted list containing elements of both lists. Original lists must stay as they were.

Had the input sorted linked lists been as shown below

img

Then, the merged linked list would look like Figure 2.

img
Approach :

We initially put 2 pointers: "one" and "two" at the head of the linked lists.

img

We make a new list for storing the resultant linked list "res".

Now, we compare the values at both the pointers. The smaller value is added at the last of "res" and its pointer is increased by one step.

In our example, values at "one" and "two" are compared. Since 7<10, therefore 7 is added to the last of "res" and "two" is moved by one step as shown in figure 4.

img

Again we compare the values at the pointers. Since 9<10, so 9 is added to the last of "res" and the "two" pointer is increased again.

img

Again on comparing, 10<12, so "one" is increased and 10 is added to the last of "res".

img

This process keeps repeating until one of the linked lists i.e. the list of smaller size reaches null. At that time the positions will look like as shown in figure 7.

img

Then, the remaining elements of the other larger linked list are added to "res" as they are already sorted and greater than the elements of the previous linked list.

Here, since "one" pointer reaches null and 60 is left in the other list, therefore 60 is added to "res".

Can you code this algorithm on your own? Take hints from the code given below if you get stuck.

import java.io.*; import java.util.*; public static LinkedList mergeTwoSortedLists(LinkedList l1, LinkedList l2) { Node one=l1.head; Node two=l2.head; LinkedList res=new LinkedList(); while(one!=null && two!=null){ if(one.data< two.data){ res.addLast(one.data); one=one.next; }else{ res.addLast(two.data); two=two.next; } } while(one!=null){ res.addLast(one.data); one=one.next; } while(two!=null){ res.addLast(two.data); two=two.next; } return res; }
java; true";
Analysis:
Time Complexity:

O(n)

Time complexity is linear due to the use of "while loop" in the code.

Space Complexity:

O(n)

The space complexity of a linked list is of order n as it increases linearly with the increase in the number of nodes.

We highly suggest you watch the solution video for a better understanding of this problem.

We conclude this question here. See you in the next question.

Linked lists
Author: Shreeya Gupta
 
Run
Id Name