Write a function to merge two doubly linked lists The input

Write a function to merge two doubly linked lists. The input lists have their elements in sorted order, from lowest to highest. The output list should also be sorted from lowest to highest. Your algorithm should run in linear time on the length of the output list. Provide an algorithm for your function Implement and show some samples of your running function

Solution

ALGORITHM for Merging two sorted lists:
1. Create a mergeNext node which points to smaller head.
2. Keep traversing the lists, node by node.
   If
       first list element is smaller, point mergedNext node to first list element and move first list forward by one node
   else
       point mergedNext to second list element.

  
IMPLEMENTATION using two sample sorted lists:

   public class LinkedList {
   Node head;
  
   // Add a new node to the front of the list
   public void addToFront(int data) {
   Node n = new Node(data);
   n.next = head;
   head = n;
   }
  
   // Print the list elements
   public void printList() {
   Node tmp = head;
   while(tmp != null) {
   System.out.print(tmp.data + \" \" );
   tmp = tmp.next;
   }
   System.out.println();
   }
  
   // Merging 2 sorted lists to form a single sorted list
   public void mergeList(LinkedList list) {
  
   if(list == null || list.head == null) {
   return;
   }
   if(head == null) {
   head = list.head;
   return;
   }
  
   Node tmp1 = head;
   Node tmp2 = list.head;
   if(tmp1.data < tmp2.data) {
   head = tmp1;
   tmp1 = tmp1.next;
   } else {
   head = tmp2;
   tmp2 = tmp2.next;
   }
   Node mergedNext = head;
  
   while(tmp1 != null && tmp2 != null) {
   if(tmp1.data < tmp2.data) {
   mergedNext.next = tmp1;
   tmp1 = tmp1.next;
   } else {
   mergedNext.next = tmp2;
   tmp2 = tmp2.next;
   }
   mergedNext = mergedNext.next;
   }
  
   if(tmp1 != null) {
   mergedNext.next = tmp1;
   } else {
   mergedNext.next = tmp2;
   }
   }
  
   public static void main(String[] args) {
   LinkedList list1 = new LinkedList();
   list1.addToFront(9);
   list1.addToFront(8);
   list1.addToFront(6);
   list1.addToFront(5);
   list1.addToFront(4);
   list1.addToFront(2);
  
  
   LinkedList list2 = new LinkedList();
   list2.addToFront(7);
   list2.addToFront(3);
   list2.addToFront(1);
  
   //Print both sorted lists
   System.out.print(\"List1 is: \" );
   list1.printList();
   System.out.print(\"List2 is: \" );
   list2.printList();
  
   //Calling mergeList function
   list1.mergeList(list2);
  
   System.out.print(\"Merged List: \" );
   list1.printList();
   }
   }
  
   class Node {
   int data;
   Node next;
  
   public Node(int data) {
   this.data = data;
   }
   }

TIME COMPLEXITY is O(n+m) which is linear time.