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:

Recursive Solution

Without Recursion

Github Link

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

    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?