アルゴリズム 体操15

Merge Two Sorted Linked Lists (Easy)

説明

2つの昇順にソートされたSingly Linked Listが引数として渡されます。
それら二つをマージして、昇順にソートされたLinked Listのheadを返り値として返すアルゴリズム。

例

以下のような二つのLinked Listがあります。

この二つのLinked List をソートを維持してマージすると以下のような単一のLinked Listにする。

Solution

Runtime Complexity O(m + n)

二つのポインタを使って二つのLinked Listに対して線形走査するので
m,nをそれぞれのLinked Listの長さとして、実行時間はO(m + n)となります。

Space Complexity O(1)

ポインタのにを使用するのでメモリはO(1)となります。

実装

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