Algorithmus Gymnastik 15

Merge Two Sorted Linked Lists (Easy)

Erläuterung

Eine einzeln verknüpfte Liste, die in aufsteigender Reihenfolge sortiert ist, wird als Argument übergeben. Ein Algorithmus, der die beiden zusammenführt und den Kopf der verknüpften Liste in aufsteigender Reihenfolge als Rückgabewert sortiert zurückgibt.

Beispiel

Es gibt zwei verknüpfte Listen wie unten. Wenn diese beiden verknüpften Listen unter Beibehaltung der Sortierung zusammengeführt werden, werden sie wie unten gezeigt zu einer einzigen verknüpften Liste. Solution Runtime Complexity O(m + n) Da es zwei Zeiger verwendet, um einen linearen Scan für zwei verknüpfte Listen durchzuführen Mit m und n als Länge jeder verknüpften Liste beträgt die Ausführungszeit O (m + n).

Space Complexity O(1) Der Speicher ist O (1), da er für den Zeiger verwendet wird.

Implementierung

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;
  }
}