Merge Two Sorted Lists - Different Implementations

$\mathtt{REFERENCE}$ @ LeetCode

$\mathtt{RELATED\ PROBLEM}$ @ Sort a LinkedList Using Merge Sort

Main Idea

The main idea to merge two sorted linked lists is to pick the node out of the two head nodes whose value is smaller and move that head to its next node. Selected node will be placed at the tail of the result linked list. We continue this process until we have no more nodes in either of the lists.

When one of the head becomes null, we no longer need to traverse through the other list. Because other list is already sorted and all its elements will be smaller than the elements in the resulting list (WHY?), we can simply append this list to the result list.

Obviously this can be implemented in different ways. Following are few :

Method 1

In this method:

1. If one of the list is empty, return other list.
2. Otherwise, select smaller head node and set it as Head and Tail of the result. Move head of the selected list to next.
3. Repeat, until ONE of the list is not empty, to select smaller head, move head to next and append the selected node to the Tail of the result.
   1. At any time, if one of the head becomes null, append other list to the tail of the result.
4. Return Head

  /**
   * Merge Two sorted Linked Lists
   * @param l1 first sorted linked list
   * @param l2 second sorted linked list
   * @return Head of the sorted linked list
   */
  ListNode merge(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;

    ListNode head, tail;
    // initialize the head and tail node of result list with one of the heads of two given lists
    if (l1.val < l2.val) {
      head = tail = l1;
      l1 = l1.next;
    } else {
      head = tail = l2;
      l2 = l2.next;
    }
    while(l1 != null || l2 != null) {
      if (l1 == null) {
        // if l1 is null, we can append l2 to the result and we are done
        tail.next = l2;
        break;
      }

      if (l2 == null) {
        // if l2 is null, we can append l1 to the result and we are done
        tail.next = l1;
        break;
      }

      // otherwise select and append smaller of the two head nodes
      if (l1.val < l2.val) {
        tail.next = l1;
        tail = l1;
        l1 = l1.next;
      } else {
        tail.next = l2;
        tail = l2;
        l2 = l2.next;
      }
    } // end while

    return head;
  } // merge
    

Method 2

In this method:

1. If one of the list is empty, return other list.
2. Otherwise, select smaller head node and set it as Head and Tail of the result. Move head of the selected list to next.
3. Repeat, until BOTH of the list is not empty, to select smaller head, move head to next and append the selected node to the tail of the result.
4. Append none empty list to the Tail of the result.
5. Return Head

  /**
   * Merge Two sorted Linked Lists
   * @param l1 first sorted linked list
   * @param l2 second sorted linked list
   * @return Head of the sorted linked list
   */
ListNode merge(ListNode l1, ListNode l2) {
  if (l1 == null) return l2;
  if (l2 == null) return l1;

  ListNode head, tail;
  // initialize the head and tail node of result list with one of the heads of two given lists
  if (l1.val < l2.val) {
    head = tail = l1;
    l1 = l1.next;
  } else {
    head = tail = l2;
    l2 = l2.next;
  }
  while(l1 != null && l2 != null) {
    // select smaller node and append to Tail of the result list
    if (l1.val < l2.val) {
      tail.next = l1;
      tail = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      tail = l2;
      l2 = l2.next;
    }
  }
  // Append the remaining nodes of one list, if any
  if (l1 == null) {
    tail.next = l2;
  } else if (l2 == null) {
    tail.next = l1;
  }

  return head;
} // merge
    

Method 3 (Same Idea - But Simpler and Easier to Perceive)

In this method:

1. Initialize Head node with a dummy data and Tail node with the same node.
2. Repeat, until BOTH of the list is not empty, to select smaller head, move head to next and append the selected node to the Tail of the result.
3. Append none empty list to the Tail of the result.
4. Return Head.next

  /**
   * Merge Two sorted Linked Lists
   * @param l1 first sorted linked list
   * @param l2 second sorted linked list
   * @return Head of the sorted linked list
   */
  ListNode merge(ListNode l1, ListNode l2) {
    // Initialize a dummy node as Head and Tail
    ListNode head = new ListNode(0);
    ListNode tail = head;

    // Keep selecting smaller of two nodes and append to the Tail
    while(l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        tail.next = l1;
        tail = l1;
        l1 = l1.next;
      } else {
        tail.next = l2;
        tail = l2;
        l2 = l2.next;
      }
    }

    // Append remaining nodes of one of the lists
    if (l1 != null) {
      tail.next = l1;
    } else if (l2 != null) {
      tail.next = l2;
    }

    return head.next; // return next of the dummy node
  } // merge
    

Applications

• One of the application of this method will be to apply in Merge Sort of a Linked List where the list will be repeatedly split into half, sorted and finally merged to give the resulting sorted list.

---

---

---