Algorithm Gymnastics 15

Merge Two Sorted Linked Lists (Easy)

Description

A Singly Linked List sorted in ascending order is passed as an argument. An algorithm that merges the two and returns the head of the Linked List sorted in ascending order as the return value.

Example

There are two Linked Lists as below. When these two Linked Lists are merged while maintaining the sort, they become a single Linked List as shown below. Solution Runtime Complexity O(m + n) Since it uses two pointers to perform a linear scan on two Linked Lists The execution time is O (m + n), where m and n are the lengths of each Linked List.

Space Complexity O(1) The memory is O (1) because it is used for the pointer.

Implementation

MergeSortList.java

class mergeSortList{
  public LinkedListNode merge_sorted(LinkedListNode head1,LinkedListNode head2) {


    if (head1 == null) { // edge case
      return head2;
    } else if (head2 == null) {
      return head1;
    }
    
    LinkedListNode cur1 = head1; // pointer1
    LinkedListNode cur2 = head2; // pointer2
    LinkedListNode cur3 = null; // pointer3 for merged list
    LinkedListNode head3 = null; // head of merged list

    while (cur1 != null && cur1 != null) {
      if (head3 == null) {
        if (cur1.data < cur2.data) {
          head3 = cur1;
          cur1 = cur1.next;
        } else {
          head3 = cur2;
          cur2 = cur2.next;
        }
        cur3 = head3;
      } else {
        if (cur1.data < cur2.data) {
          cur3.next = cur1;
          cur1 = cur1.next;
        } else {
          cur3.next = cur2;
          cur2 = cur2.next;
        }
        cur3 = cur3.next;
      }
    }
    
    if (cur1 != null) {
      cur3.next = cur1;
    } else {
      cur3.next = cur2;
    }
  
    return head3;
  }
}