[leetcode]21. Merge Two Sorted Lists

두개의 정렬된 링크드 리스트 list1, list2의 Head를 받았다.(리스트가 아니라, 연결리스트의 헤드라는 것!)

두개의 리스트를 하나의 정렬된 리스트로 반환하기.
splicing을 통해서 만들어져야한다.
이게 무슨말이지? 싶다면 연결리스트를 배워야한다.
https://www.algodale.com/data-structures/linked-list/

링크드 리스트란
소위 노드라 일컫는 객체의 일부로 데이터를 저장한다.
각 노드에서는 다음 노드를 가리키고 있는 레퍼런스 또는 포인터도 함께 저장되어있다.

하나의 노드에는 2개의 정보가 있다.
1. 데이터 : value
2. 다음 노드의 레퍼런스 : next

처음부터 끝까지 탐색하기 적합한 구조를 갖고 있다.

배열과 상당히 유사하지만, 차이가 있다.
배열은 크기가 고정. 데이터를 추가하거나 삭제하는데에 불리한 자료구조이다.

메모리 상의 연속된 영역을 차지하기 때문에 유연하게 크기를 줄이거나 늘이기가 어려운 구조이기 때문이다.
대신, 인덱스를 통해 빠르게 접근이 가능하다.

반면 링크드 리스트는, 크기에 제한이 없으며,
데이터를 추가하거나 삭제하기 유리한 자료구조이다.
메모리 상에서 좀 더 자유롭게 위치할 수 있다.

배열: 데이터 무작위 접근에 최적화 되어있다. 대신 맨 첫번째 노드부터 원하는 것까지 순회하는 것 까지 O(n)이 걸린다.
링크드리스트: 하지만, 추가 삭제에 강점이 있다.

현재 문제에서

/**
 * 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}
 */
function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null,
): ListNode | null {
  if (!(list1 && list2)) return list1 || list2;
  if (list1.val < list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
}

두개의 리스트에 대해서 재귀를 돈다.
만약에 둘다 없으면 , 둘중의 하나를 돈다.

list1.val이 list2.val보다 작으면
list1.next 다음에 list2.val이 온다.
만약 아니라면,
list2.next 다음에 list1이 이온다.

이렇게 순회를 하면서 붙여주는 것이다.