[JS/알고리즘] Merge Two Sorted Lists

Linked List + Merge Sort

Merge sort의 기본개념은 Divide and conquer이다.
따라서 Quick sort와 마찬가지로 재귀를 통해 구현 할 수 있다.

 

이미 정렬된 두 파티션들이 있다면,
두 파티션의 첫요소를 검사하여 더 작은 요소를 뺀다.

Linked List 와 연결하여서 푸는 문제이기때문에
더 작은 요소를 가지고 있는 링리를 헤드로 삼고, 
헤드로 삼은 링리의 다음 노드와, 헤드가 되지못한 링리 두가지를 다시 함수에 넣는다.

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new sorted list.

The new list should be made by splicing together the nodes of the first two lists.

Example:
Input: 1->2->4, 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} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */

const mergeTwoLists = function(l1, l2) {
  if (!l1) return l2;
  if (!l2) return l1;

  if(l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
};

 

출처 : leetcode.com/problems/merge-two-sorted-lists/