LeetCode 21. Merge Two Sorted Lists

Merge Two Sorted Lists

문제

문제 설명

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Linked List를 사용하여 두 list를 오름차순으로 병합하는 문제.

입출력 예

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Input: list1 = [], list2 = []
Output: []

Input: list1 = [], list2 = [0]
Output: [0]

제한 사항

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

풀이

나의 풀이

1. l1이 비어있다면 l2를, l2가 비어있다면 l1을 반환
2. 임시로 사용할 시작 노드 생성
3. l1의 value와 l2의 value를 비교하여 더 작은 값을 현재 노드인 current에 연결하는 작업 반복 (두 연결 리스트가 모두 존재할 때까지만)
4. l1 혹은 l2가 비어있지 않다면, 비어있지 않은 연결 리스트의 나머지 노드들을 current에 연결.
5. 첫 번째 노드는 임시로 만든 시작 노드이므로, 다음 노드를 헤드로 return

// Runtime: 54 ms, faster than 99.94%
// Memory Usage: 44.3 MB, less than 36.58%

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
  if (!l1) return l2;
  if (!l2) return l1;
  
  let ll = new ListNode(-101);
  let current = ll;

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

    current = current.next;
  }

  if (l1 !== null) current.next = l1;
  else if (l2 !== null) current.next = l2;

  return ll.next;
};

다른 사람들의 풀이

반복문을 돈 후에 비어있지 않은 연결 리스트를 current에 연결할 때 OR 연산자 ||를 이용하면 더 간결하게 작성할 수 있다.

var mergeTwoLists = function(l1, l2) {
  let ll = { val: -1, next: null };
  let current = ll;

  while (l1 && l2) {
    if (l1.val > l2.val) {
      current.next = l2;
      l2 = l2.next;
    } else {
      current.next = l1;
      l1 = l1.next;
    }

    current = current.next;
  }

  current.next = l1 || l2;

  return ll.next;
};

재귀 함수를 이용한 풀이

var mergeTwoLists = function(l1, l2) {
  if(!l1 || !l2) return (l1? l1:l2);
  if(l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
};

구조 분해 할당으로 무조건 작은 값이 첫 번째 리스트의 value가 될 수 있도록 만들어서 재귀함수 한 번만 호출

var mergeTwoLists = function(h1, h2) {
  // return the non-empty one
  if (!h1 || !h2) return h1 || h2;

  // swap to make sure h1 is always smaller than h2
  if (h1.val > h2.val) [h1, h2] = [h2, h1];
    
  h1.next = mergeTwoLists(h1.next, h2);
  
  return h1;
};

WIL

구조 분해 할당

ES6의 구조 분해 할당 문법을 이용하면 두 변수를 swap 할 수 있다.

let a = 5, b = 10;
[a, b] = [b, a];
console.log(a, b); // 10 5