# Merging two Sorted Singly Linked List

## Introduction – Merging two Sorted Singly Linked List

This question is mostly asked in interviews and hence I thought of writing few possible solutions to the same. I also asked the same question on stackoverflow.com. You can visit the link here

## Problem Statement

You have two singly linked lists that are already sorted, you have to merge them and return the head of the new list without creating any new extra nodes. The returned list should be sorted as well

The method signature is:

Node class is below:

## Solution

There can be multiple solutions to the given problem, few of them are given below:

## Conclusion

Here we learnt to merge two sorted singly linked list without creating any another list. This problem can be solved using recursion, which I personally like. For the non-recursion lovers there is another program written above.

Hope this helps. Stay connected and stay Subscribed

• Holden

I mean do you have something like this in your node class?
public void next(Node n){
next = n;
}

• this is done… hope it helps

• Holden

in solution without recursion, the 'head' node which you have created and also 'Node tmp' don't violate this condition of problem statement: "without creating any new extra nodes"?

• No new node is created… its just two new reference variables. Nodes can only be created when we use the <code>new</code> operator. ðŸ™‚

So, the condition is not violated.

• Holden

Thank you for your reply. but what do mean by "Nodes can only be created when we use the new operator."?

• In Java we say that an object is created only when we use the constructor of the object.
<code>Node node = new Node()</code> is a valid statement to create a node.

But when I write <code>Node tmp = node;</code> I am just pointing the tmp reference variable to the already created node.

So, you cannot say that another node is created in the assignment statement.

• Holden

thank you so much. it's clear now ðŸ™‚

• Holden

BTW, thank you for your neat and elegant solutions ðŸ™‚ Best wishes

• You are always welcome, thanks for following.

• Holden

Method 2 (without recursion) never terminates, right?

• Your code and the code in the post are exactly the same. I have added two github links with fully running code versions. You can download them and run the main method to verify again. ðŸ™‚

• Holden

• check in the post.. Just above the Conclusion heading.

• Holden

Thank you. I don't know why i cannot see the links. anyway, thank you

• Cipher()

can anyone please explain me how the recursion solution is working, i got the other one(Iterative Approach)

• Think it this way!

What does the recursive method returns?
It returns the head of the merged linked list every time we pass it two linked lists.

Now, look at the recursion, if the head of list1 is smaller than the head of list2, then the head of list1 remains as is, and we recursively merge the the list2, with the remaining list1 and vice versa..

Let me know if this still is not understandable. I will suggest you to draw recursion stack and nodes on paper once.

• Ghanshyam Gupta

Thanks for the explanation. But how would you suggest to approach any such recursive problems? I do face difficulty in understanding recursive code. Any suggestions?

• Hi Ghanshyam,

Apologies for the delayed response. Here is my small suggestion on how to think recursively. I have written a very basic recursion post. You can find it here : http://techieme.in/recursion/