leetcode0021 - Merge Two Sorted Lists / Easy / Typescript

https://leetcode.com/problems/merge-two-sorted-lists/

Merge Two Sorted Lists - LeetCode

Time Complexity O(N + M)

• list Node 두 개의 각각 길이 N, M 만큼 소요

Space Compexity O(1)

• 따로 변수를 만들지 않기 때문에 공간 복잡도는 O(1)

재귀함수 사용

• 재귀를 사용 하여 작은 값의 노드 next 로 재귀함수를 호출한다.
  • 두 개의 노드 리스트의 각 첫번째 노드들을 비교하여 값의 대소를 비교한다.
  • 값이 작은 노드의 next로 또 재귀함수를 호출해서 받은 값을 달아준다. 이렇게 반복하면, 왼쪽부터 가장 작은 값으로 쌓이게 된다.
• listNode1의 첫번째 값이 listNode2의 첫번째 값보다 작은 경우
  • listNode1의 다음 값은 (listNode.next와 listNode2를 합친 listNode)
  • 즉 mergedList는 [listNode1.head, listNode1.next 와 listNode2.head 중 작은 값, listNode1.next와 listNode2.next 중 작은 값, ...., ]
• listNode2의 첫번째 값이 listNode1의 첫번째 값보다 작은 경우
  • listNode2의 다음 값은 (listNode1와 listNode2.next를 합친 listNode)
  • 즉 mergedList는 [listNode2.head, listNode1.head와 listNode2.next 중 작은 값, ...., ]

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    if(list1 === null) return list2; 
    if(list2 === null) return list1;

    if(list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } 

    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
};