Merge Two Sorted Linked Lists (Easy)

설명

두 개의 오름차순으로 정렬된 Singly Linked List가 인수로 전달됩니다.
둘을 병합하여 오름차순으로 정렬 된 링크 된 목록의 머리를 반환 값으로 반환하는 알고리즘.

예

다음과 같은 두 개의 링크된 목록이 있습니다.

이 두 개의 링크 된 목록을 정렬을 유지하고 병합하면 다음과 같은 단일 링크 된 목록이됩니다.

Solution

Runtime Complexity O(m + n)

두 개의 포인터를 사용하여 두 개의 링크 된 목록에 대해 선형 스캔하기 때문에
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;
  }
}