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 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:


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

Recursive Solution

Without Recursion

Github Link


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

    Could you please write your getters and setters in your Node class, as well?
    I mean do you have something like this in your node class?
    public void next(Node n){
    next = n;

  • 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?

  • 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 :

          Read this and if you still find difficulties, I promise to help you.