Merge 2 Sorted Linked Lists

Merge 2 Sorted Linked Lists

Merge 2 Sorted Linked Lists  

Function that takes two lists, each of which is sorted in increasing order, and merges the two together into one list which is in increasing order. The new list should be made by splicing
together the nodes of the first two lists.

For example if the first linked list a is 5->10->15 and the other linked list b is 2->3->20, then SortedMerge() should return a pointer to the head node of the merged list 2->3->5->10->15->20.

There are many cases to deal with: either ‘a’ or ‘b’ may be empty, during processing either ‘a’ or ‘b’ may run out first, and finally there’s the problem of starting the result list empty, and building it up while going through ‘a’ and ‘b’.

{ 3, 6, 7, 8, 9 }
{ 1, 5, 7, 10, 89 }
OUTPUT: 1, 3, 5, 6, 7, 7, 8, 9, 10, 89

{}
{3, 4, 7, 8}
OUTPUT: 3, 4, 7, 8

Lets see simple Java code to get merge 2 sorted linked list without creating new (3rd) linked list and only by splicing both list nodes.

class NODE {
 
 int data;
 NODE next;

 public NODE(int data) {
  this.data = data;
  this.next = null;
 }
}

public class MergeLinkedList {

 public static void main(String[] args) {

  MergeLinkedList obj = new MergeLinkedList();

  int val1[] = new int[] { 3, 6, 7, 8, 9 };
  int val2[] = new int[] { 1, 5, 7, 10, 89 };

  /* Create 1st linked list */
  NODE firstListStart = obj.createLinkedList(val1);
  
  /* Create 2nd linked list */
  NODE secondListStart = obj.createLinkedList(val2);

  /* Merge both linked list without 3rd linked list */
  NODE start = obj.mergeLinkedList(firstListStart, secondListStart);

  NODE print = start;
  while (print != null) {
   System.out.println("----> " + print.data);
   print = print.next;
  }
 }

 /*
  * Create linked list based on given array
  */
 public NODE createLinkedList(int val[]) {
  NODE start = null;
  for (int i : val) {
   NODE tmp = new NODE(i);
   if (start == null) {
    start = tmp;
   } else {
    NODE mover = start;
    while (mover.next != null) {
     mover = mover.next;
    }
    mover.next = tmp;
   }
  }
  return start;
 }

 /*
  * Merge both the linked list without creating new Linked List.
  */
 public NODE mergeLinkedList(NODE first, NODE second) {

  if (first == null)
   return second;
  if (second == null)
   return first;

  NODE start = null;
  NODE mover = null;

  while (first != null && second != null) {
   if (start == null) {
    if (first.data <= second.data) {
     start = mover = first;
     first = first.next;
    } else if (second.data <= first.data) {
     start = mover = second;
     second = second.next;
    }
   } else {
    if (first.data <= second.data) {
     mover.next = first;
     first = first.next;
    } else if (second.data <= first.data) {
     mover.next = second;
     second = second.next;
    }
    mover = mover.next;
   }
  }
  if (first == null) {
   while (second != null) {
    mover.next = second;
    second = second.next;
    mover = mover.next;
   }
  }
  if (second == null) {
   while (first != null) {
    mover.next = first;
    first = first.next;
    mover = mover.next;
   }
  }
  return start;
 }
}

OUTPUT:

----> 1
----> 3
----> 5
----> 6
----> 7
----> 7
----> 8
----> 9
----> 10
----> 89