Merging two sorted linked list of unequal length

Question

I was trying out the merging of two sorted linked list.

The code snippet doesn't work for below two list :

List 1 : 1->3->5->7->9->null
List 2 : 2->4->6->8->10->null

Expected List : 1->2->3->4->5->6->7->8->9->10->null

But the output for below programs turns out to be this :

Output :  1->2->3->4->5->6->7->8->9->null // element 10 is missing.

Am I missing something ? Live Demo : http://ideone.com/O7MBlo

class Node {

    Node next;
    int value;

    Node(int val) {
        this.value = val;
        this.next = null;
    }

    @Override
    public String toString() {
        Node cur = this;
        String str = "";

        while(cur != null) {
            str += cur.value+"->";
            cur = cur.next;
        }

        return str;
    }
}

class MergeLL {

    public static Node merge(Node n1, Node n2) {

        Node result = null;

        if(n1 != null && n2 != null) {
            if(n1.value < n2.value) {
                result = n1;
                result.next = merge(n1.next, n2);
            } else {
                result = n2;
                result.next = merge(n1, n2.next);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n3 = new Node(3);
        Node n5 = new Node(5);
        Node n7 = new Node(7);
        Node n9 = new Node(9);

        n1.next = n3;
        n3.next = n5;
        n5.next = n7;
        n7.next = n9;
        n9.next = null;

        Node n2 = new Node(2);
        Node n4 = new Node(4);
        Node n6 = new Node(6);
        Node n8 = new Node(8);
        Node n10 = new Node(10);

        n2.next = n4;
        n4.next = n6;
        n6.next = n8;
        n8.next = n10;
        n10.next = null;

        System.out.println("Merge : " + merge(n1, n2));
    }
}

Solution 1

You need to add two more conditions, for when either n1 or n2 exhausts earlier. So, your condition - n1 != null && n2 != null, will only work in the case when both the list are of same size.

Just add code for below two conditions, after that if:

if(n1 != null && n2 != null) {
        if(n1.value < n2.value) {
            result = n1;
            result.next = merge(n1.next, n2);
        } else {
            result = n2;
            result.next = merge(n1, n2.next);
        }

} else if (n1 != null) {  
    result = n1;  // Add all the elements of `n1` to `result`
} else if (n2 != null) {
    result = n2;  // Add all the elements of `n2` to `result`
}

---

Actually, you don't need to build a new result list there. You can simply extend one of the passed Nodes.

You can modify your method as below:

public static Node merge(Node n1, Node n2) {
    if (n1 == null) return n2;
    if (n2 == null) return n1;

    if (n1.value < n2.value) {
        n1.next = merge(n1.next, n2);
        return n1;
    } else {
        n2.next = merge(n2.next, n1);
        return n2;
    }
}

Solution 2

A recursive algorithm has a base condition.So your base condition are:

• empty list n1 and n2
• n1 empty and n2 not empty.
• n2 empty and n1 empty.

Handle your base conditions 2 and 3 well as:

In condition 2, base condition is n2 empty so we will return n1:

else if(n1!=null ){
        result=n1;
    }

In condition 3, base condition is n1 empty so we will return n2:

else if(n2!=null ){
        result=n2;
    }

Hence problem is in design of your base conditions in algorithm!!

So try this, it surely works

public static Node merge(Node n1, Node n2) {
    Node result = null;

    if(n1 != null && n2 != null) {
        if(n1.value < n2.value) {
            result = n1;
            result.next = merge(n1.next, n2);
        } else {
            result = n2;
            result.next = merge(n1, n2.next);
        }

    }
    else if(n1!=null ){
        result=n1;
    }
    else if(n2!=null){
        result=n2;
    }
    return result;
}

Good luck!!

Edit: This link should help you in designing recursive algorithms.

Solution 3

if(n1 != null && n2 != null) {

What happens when one of the lists is null but the other one is not?

It returns null. But instead it should return the list that is not null.

A possible solution would be like;

if(n1 == null)
  return n2;
if(n2 == null)
  return n1;

if(n1.value < n2.value) {
  result = n1;
  result.next = merge(n1.next, n2);
  } else {
  result = n2;
  result.next = merge(n1, n2.next);
}

Solution 4

Solution for Merge Two Sorted linkedlist: https://leetcode.com/problems/merge-two-sorted-lists/

While loop will execute till one of the list finish , remaining data of another list will append later outside the while loop.

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(0);
            ListNode head = dummy;

            while(l1 != null && l2 != null) {
                if(l1.val <= l2.val) {
                    dummy.next = l1;
                    l1 = l1.next;
                }else{
                    dummy.next = l2;
                    l2 = l2.next;
                }

                dummy = dummy.next;
            }

            if(l1 != null) {
                dummy.next = l1;
            }else {
                dummy.next = l2;
            }

            return head.next;
        }
    }

View more solutions