21. Merge Two Sorted Lists

💡 풀이

// General Solution
function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

var mergeTwoLists = function (l1, l2) {
  let merge = new ListNode();
  let head = merge;

  while (l1 && l2) {
    // 각 Linked List에서 가장 작은 value를 선택한 뒤
    // !!어차피 정렬이 되어 있으니 맨 앞에 있는 요소가 가장 작은 value이다.
    // next를 통해 이어준다. (Singly Linked List니까)
    if (l1.val < l2.val) {
      
      // 헷갈렸던 부분!
      merge.next = l1; // l1 자체가 Linked List이기 때문에 처음 node는 head인 1이된다.
      l1 = l1.next;
    } else {
      merge.next = l2; // ?
      l2 = l2.next;
    }
    merge = merge.next;
  }

  // Linked List의 크기가 다른 경우
  //node의 수가 더 작은 list의 next가 더 큰 list의 node를 바라보게 한다.
  if (!l1) merge.next = l2;
  else if (!l2) merge.next = l1;

  return head.next;
};

// Recurisve Solution
var mergeTwoLists = function (l1, l2) {
  if (!l1 || !l2) return l1 ? l1 : l2;

  // 위와 로직은 동일. 단지 Recursive로 풀었을 뿐.
  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
};

📝 정리

Linked List를 실제 문제에서 접한 건 처음이었다. 혼자 못 풀었지만 다행히 Dicussion을 보고 이해할 수 있는 수는 있었다.

• 가장 헷갈렸던 부분이 merge.next = l1부분 이었는데, 이는 내가 Input에서 보여지는 것처럼(l1=[1,2,4]) 단순하게 l1을 배열로 생각했기 때문이었다.

• 내 의문: merge.next = l1를 할 경우, head의 다음 node는 배열 전체를 가리키게 될 텐데, 왜 이런 답이 가능한걸까? 였다.

• 해결: 스터디원분 중 한 분의 설명을 듣고 이해를 했다. l1의 자료구조를 배열이 아니라 Linked List로 생각해야 한다는 것이다. merge.next = l1 그럼 이 코드 자체가 처음 loop을 돌 때, head의 다음 node인 1을 가리키게 된다. (감사합니다..!)

추가

• 난 자료구조 기본과 알고리즘 문제 풀이를 JS로 시작했기 때문에, 다른 정적 언어에서는 당연시 되는 '배열의 길이 지정'을 해주지 않았다. ex) let array = []

• JS에서는 배열(난 동적 자료구조로 이해했다)에 원소를 추가, 삭제할 수 있는 push, pop, shift, unshift 등의 메소드를 사용하면 배열의 길이 또한 자동으로 늘리거나 줄여주기 때문에, JS의 배열은 Array와 Linked List의 특성을 동시에 가지고 있다고 할 수 있다. (Java의 ArrayList와 작동이 비슷한 듯)

문제 링크
https://leetcode.com/problems/merge-two-sorted-lists/

LeetCode GitHub
https://github.com/tTab1204/LeetCode/tree/main/%EC%A3%BC%EC%98%81