21. Merge Two Sorted Lists

21. Merge Two Sorted Lists
23. Merge k 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.

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

Single Linked List

Linked List(이하 연결 리스트)의 종류로 단방향 리스트이다. 노드는 노드의 데이터 필드(value)와 다음 노드에 대한 참조(next)를 가진다.

array는 요소를 삽입/삭제하는 과정에서 비용이 많이 드는데 비해 연결리스트는 포인터를 바꿔주므로 비교적 용이하다. (포인터를 위한 추가 메모리는 필요)

하지만, 포인터를 위한 추가 메모리가 소모되며, 렌덤으로 요소에 엑세스가 불가능하다. (헤드 노드부터 순차적으로 접근) 요소 검색과 정렬은 포인터를 옮길 때 복잡하고 비용이 많이 드는 단점이 있다.

풀이 과정

A리스트와 B리스트를 비교(사진 1~6번)해 값이 작은 노드의 next(다음 연결된 노드)와 큰 노드를 재귀적으로 비교한다. 각 리스트를 전부 순회하면 마지막에 가리키는 포인터는 null이 되므로 base case에 부합해 노드를 역으로 return한다.

base case 조건을 만났을 때, 재귀를 탈출하면서 return 된 노드는 이전 비교했던 노드 중 작은 값의 next 노드가 된다.

코드를 보면 이해가 쉽다.

코드

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

/**
 * 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(list1, list2) {
  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
  }
};

Advanced

비슷한 유형의 문제로 Merge k Sorted Lists가 있는데, 두개의 연결리스트가 아니라 k개의 연결리스트를 합쳐서 정렬해야 한다. 접근이 잘 안되어 힌트를 보곤 두개씩 쪼개면 되는구나 싶었다.

function mergeTwoLists (list1, list2) {
  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
  }
}

var mergeKLists = function(lists) {
  if (!lists.length) return null;

  for (let i = 1; i < lists.length; i++) {
    lists[0] = mergeTwoLists(lists[0], lists[i])
  }
  return lists[0]
};

lists[0]와 lists[i] 를 병합 & 정렬하여 lists[0]에 누적한다.

---

출처

• what-is-linked-list | geeksforgeeks
• 21. Merge Two Sorted Lists
• 23. Merge k Sorted Lists