LeetCode 21 - Merge Two Sorted Lists (Easy)

문제

LeetCode - 21번

풀이 과정

병합 정렬 의 병합 과정을 직접 구현해보는 문제입니다.

병합 정렬 은 각각의 배열 요소를 균등하게 나누고 나누어진 배열을 정렬하여 합치는 분할정복 을 사용하는 정렬 알고리즘입니다.
두 배열이 모두 정렬된 상태이기 때문에 배열의 가장 앞 요소부터 서로 비교해주며 작은 요소들을 하나씩 추가해나가면 됩니다.

만약 둘 중 하나의 배열이 비어있을 경우에는 비어있지 않은 배열을 그대로 이어붙이면 됩니다.
입력으로 둘 중 한 배열이 비어있는 것이 존재할 수 있으므로 이 부분에 대해 별도의 예외처리를 진행해줬습니다.

코드

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
  let head = null;
  let tail = null;

  if (!l1 || !l2) {
    return l1 ? l1 : l2;
  }

  while (l1 && l2) {
    if (l1.val < l2.val) {
      if (!head) {
        head = new ListNode(l1.val);
        tail = head;
      } else {
        tail.next = new ListNode(l1.val);
        tail = tail.next;
      }

      l1 = l1.next;
    } else {
      if (!head) {
        head = new ListNode(l2.val);
        tail = head;
      } else {
        tail.next = new ListNode(l2.val);
        tail = tail.next;
      }

      l2 = l2.next;
    }
  }

  if (l1) tail.next = l1;
  if (l2) tail.next = l2;

  return head;
};