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. Screen Shot 2020-01-11 at 13.08.56.png When these two Linked Lists are merged while maintaining the sort, they become a single Linked List as shown below. Screen Shot 2020-01-11 at 13.10.58.png 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;
  }
}


Recommended Posts

Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm exercise 6
Algorithm Gymnastics 24 Reverse a Linked List
Python algorithm
Algorithm exercises 13
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 24 Middle of the Linked List
Python memorandum (algorithm)
Dictionary learning algorithm
String search algorithm