content: package linkedlist;
  
  public class MergeLinkedList {
  
      /*
       * Given two sorted linked lists, merge them such that resulting linked list is also sorted.
       * Input: List1: 4, 8, 15, 19        List2: 7, 9, 10, 16
       * Output:  4, 7, 8, 9, 10, 15, 16, 19
       *
       * */
  
      /*
       * Runtime Complexity:
       * Linear, O(m + n) where m and n are lengths of both linked lists.
       *
       * Memory complexity:
       * Constant, O(1)
       *
       *
       * */
      public static LinkedList.Node mergeSorted(LinkedList.Node head1,
                                                LinkedList.Node head2) {
  
          // if both lists are empty then merged list is also empty
          // if one of the lists is empty then other is the merged list
          if (head1 == null) {
              return head2;
          } else if (head2 == null) {
              return head1;
          }
  
  
          LinkedList.Node mergedHead = null;
          if (head1.data <= head2.data) {
              mergedHead = head1;
              head1 = head1.next;
          } else {
              mergedHead = head2;
              head2 = head2.next;
          }
  
          LinkedList.Node mergedTail = mergedHead;
  
          while (head1 != null && head2 != null) {
              LinkedList.Node temp = null;
              if (head1.data <= head2.data) {
                  temp = head1;
                  head1 = head1.next;
              } else {
                  temp = head2;
                  head2 = head2.next;
              }
  
              mergedTail.next = temp;
              mergedTail = temp;
          }
  
          if (head1 != null) {
              mergedTail.next = head1;
          } else if (head2 != null) {
              mergedTail.next = head2;
          }
  
          return mergedHead;
      }
  
  
  
      public static class LinkedList {
  
          private Node head;
  
          public Node head() {
              return head;
          }
  
          public void printNode(Node node) {
              while (node != null) {
                  System.out.print(node.data + " ");
                  node = node.next;
              }
          }
  
          /* Inserts a new Node at end of the list. */
          public void push(int new_data) {
              Node newNode = new Node(new_data);
              if (head == null) {
                  head = new Node(new_data);
                  return;
              }
  
              newNode.next = null;
              Node last = head;
              while (last.next != null) {
                  last = last.next;
              }
              last.next = newNode;
          }
  
          public static class Node {
              private Node next;
              private Integer data;
  
              public Node(Integer data) {
                  this.data = data;
              }
  
              public Node next() {
                  return next;
              }
  
              public void setNext(Node next) {
                  this.next = next;
              }
  
              public Integer data() {
                  return data;
              }
  
              public void setData(Integer data) {
                  this.data = data;
              }
          }
      }
  
  
      public static void main(String[] args) {
          LinkedList linkedList1 = new LinkedList();
          linkedList1.push(4);
          linkedList1.push(8);
          linkedList1.push(15);
          linkedList1.push(19);
  
  
          LinkedList linkedList2 = new LinkedList();
          linkedList2.push(7);
          linkedList2.push(9);
          linkedList2.push(10);
          linkedList2.push(16);
  
          System.out.println("List 1: ");
          linkedList1.printNode(linkedList1.head);
          System.out.println();
          System.out.println("List 2: ");
  
          linkedList2.printNode(linkedList2.head);
          System.out.println();
  
          LinkedList.Node mergedList = mergeSorted(linkedList1.head, linkedList2.head);
          linkedList2.printNode(mergedList);
      }
  }
  