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));
    }
}

What about adding all elements to a single collection, sort it then loop to update attribute `next` ? — Arnaud Denoyelle, Jul 19 '13 at 11:55
@ArnaudDenoyelle: The sort is O(n log n). A straight merge is O(n). The difference is huge when you have, say, a million items. — Jim Mischel, Feb 23 '16 at 14:12
By the way, there is a huge drawback to a recursive merge: stack space. Absent tail recursion removal, the recursive merge will consume O(n) stack frames. So you'll probably blow the stack if the total number of items in your lists is even moderately large (say, 100,0000 or so). — Jim Mischel, Feb 23 '16 at 14:20

Rohit Jain · Accepted Answer · 2013-07-19T12:06:22.660

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;
    }
}

I tried this .. else if(n1 != null) { result.next = n1; } else if(n2 != null) { result.next = n2; } .. but it throws NPE .. !! — tmgr, Jul 19 '13 at 11:54
@tm99. Updated the code. Also check the 2nd code I've posted. It would be much cleaner. — Rohit Jain, Jul 19 '13 at 12:00
Can you help me with this ? http://stackoverflow.com/questions/17748078/simplest-and-understandable-example-of-volatile-keyword-in-java — tmgr, Jul 19 '13 at 14:03

rahulserver · Answer 2 · 2013-07-19T12:07:21.727

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.

tafa · Answer 3 · 2013-07-19T11:58:06.450

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);
}

score 1 · Answer 4 · answered Sep 26 '19 at 12:42

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;
        }
    }

score 0 · Answer 5 · answered Jul 19 '13 at 11:58

It can be optimized too. Just for understanding

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;
            result.next = merge(n1.next, n2);
        }
        else if(n2 != null) {
            result = n2;
            result.next = merge(n1, n2.next);
        }
        return result;
    }

score 0 · Answer 6 · answered Oct 17 '13 at 20:44

package test;

import java.util.*;

public class TestMergeLists<T extends Comparable<? super T>>
{
    static <T extends Comparable<? super T>> List<T> merge(List<T> a,List<T>b)
    {
        Collections.sort(a);
        Collections.sort(b);
        List<T> result = new ArrayList<T>();
        int i = 0;
        int j = 0;

        for (;;)
        {
            T a1 = a.get(i);
            T b1 = b.get(j);
            if (a1.compareTo(b1) > 0)
            {
                result.add(b1);
                j++;
                if (j == b.size())// no more
                {
                    if (i < a.size() - 1)
                        result.addAll(a.subList(i + 1, a.size()));
                    break;
                }
            } else if (a1.compareTo(b1) == 0)
            {
                result.add(a1);
                result.add(b1);
                i++;
                if (i == a.size())
                {
                    if (j < b.size() - 1)
                        result.addAll(b.subList(j + 1, b.size()));
                    break;
                }
                j++;
                if (j == b.size())// no more
                {
                    if (i < a.size() - 1)
                        result.addAll(a.subList(i + 1, a.size()));
                    break;
                }
            } else
            {
                result.add(a1);
                i++;
                if (i == a.size())// no more
                {
                    if (j < b.size() - 1)
                        result.addAll(b.subList(j + 1, b.size()));
                    break;
                }
            }
        }
        return result;
    }
    public static void main(String args[])
    {
        List<String> a = new ArrayList<String>();
        a.addAll(Arrays.asList("the statement you found confusing is how MergeSort merges two ".split(" ")));
        List<String> b = new ArrayList<String>();
        b.addAll(Arrays.asList("then increment the current index for ".split(" ")));
        List<String> result = merge(a,b);
        System.out.println(result);
    }
}

score 0 · Answer 7 · answered Feb 22 '16 at 16:48

Here is Easy and Iterative (non recursive) code for merge two sorted Linked List:

import java.util.*;
class Node
{
 public int data;
 public Node next;
 Node(int x)
 {
     data=x;
     next=null;
 }
}
public class Test {
        public static Node merge(Node a, Node b)
        {
          Node res=null; 
          Node first=null;
          if(a.data < b.data)
              {
                  res=a;
                  first=a;
                  a=a.next;
              }
              else
              {   
                  first=b;
                  res=b;
                  b=b.next;
              }

          while(a!=null && b!=null)
          {
              if(a.data < b.data)
              { 
                  res.next=a;
                  res=res.next;
                  a=a.next;
              }
              else
              {  
                  res.next=b;
                  res=res.next;
                  b=b.next;
              }   
          } 
          if(a!=null)
          {
              res.next=a;
          }
          else if(b!=null)
          {
              res.next=b;
          }

          return first;
        }

        public static void display(Node first)
        {
            while(first!=null)
            {
                System.out.print(first.data+" ");
                first=first.next;
            }
        }
        public static void main(String[] args)
        {
            Node n1=new Node(4);
            Node n2=new Node(5);
            Node n3=new Node(7);
            Node n4=new Node(10);
            n1.next=n2;
            n2.next=n3;
            n3.next=n4;
            n4.next=null;

            Node n5=new Node(3);
            Node n6=new Node(6);
            Node n7=new Node(9);
            Node n8=new Node(15);
            n5.next=n6;
            n6.next=n7;
            n7.next=n8;
            n8.next=null;

            Node f = merge(n1,n5);
            display(f);
        }
}

What happens if `a` or `b` is null on entry? – Jim Mischel Feb 23 '16 at 14:15 — Jim Mischel, Feb 23 '16 at 14:15

score 0 · Answer 8 · answered Sep 13 '19 at 06:58

Merge Two Sorted Lists | Leetcode problem | Javascript Solution

class ListNode {
  constructor(val, next=null) {
    this.val = val;
    this.next = next;
  }
}

const c = new ListNode(4);
const b = new ListNode(2, c);
const a = new ListNode(1, b);
const z = new ListNode(3);
const y = new ListNode(2, z);
const x = new ListNode(1, y);

var mergeTwoLists = function(l1, l2) {

  let p1 = l1;
  let p2 = l2;
  let l3, p3;
  if(l1) {
      if (l2){
          if(p1.val < p2.val) {
            l3 = new ListNode(p1.val);
            p1 = p1.next;
          } else {
            l3 = new ListNode(p2.val);
            p2 = p2.next;
          }
      } else {
          return l1;
      }
  } else if(l2) {
      return l2;
  } else {
      return "";
  }
  p3 = l3;

  while(p1 && p2) {
    if(p1.val < p2.val) {
      p3.next = new ListNode(p1.val);
      p1 = p1.next;
    } else {
      p3.next = new ListNode(p2.val);
      p2 = p2.next;
    }
    p3 = p3.next;
  }
  if (p1) {
    p3.next = p1;
  } else {
    p3.next = p2;
  }
  return l3;
}

console.log(mergeTwoLists(a, x));

Merging two sorted linked list of unequal length

8 Answers8