Algorithm - Recursion Problems

Merge Two Sorted Lists

• 2개의 정렬된 Linked List를 하나의 Linked List로 병합하는 함수 구현

• 구현 방법

  • head라는 이름으로 Linked List를 만든다
  • list1과 list2의 value를 비교해서 더 작은 값을 head.next에 할당한다
  • 더 작은 값의 next와 큰 값에 대해 비교하기 위해 회귀 함수를 호출한다
  • list1이나 list2의 next값 둘 중 하나만 없을 경우, 있는 값을 head.next에 할당한다
  • list1과 list2의 next값이 둘 다 없을 경우, head를 반환한다
  • head를 만들 때 들어간 초기값을 없애기 위해 head에 head.next를 할당한다

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

var mergeTwoLists = function(list1, list2) {
    let head = new ListNode();
    linkNextList(list1, list2, head);
    head = head.next;
    return head;
};

Reverse Linked List

• Linked List를 거꾸로 정렬하는 함수 구현

• 구현 방법

  • node가 null이 될 때까지 모든 node를 순회한다
  • next에 node.next를 할당한다
  • node.next에 prev를 할당한다
  • prev에 현재 node를 할당한다
  • node에 다음 순서인 next를 할당한다
  • 다음 순서인 node, next, prev에 대해 회귀함수를 호출한다

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */

const helper = function(node, next, prev) {
    if (!node) {
        return prev;
    }
    next = node.next;
    node.next = prev;
    prev = node;
    node = next;
    return helper(node, next, prev);
}

var reverseList = function(head) {
    let node = head;
    let next;
    let prev = null;
    return helper(node, next, prev);
};

The Power Sum

• 주어진 지수의 제곱수의 합이 특정한 값이 되는 경우의 수를 반환하는 함수 구현

• 구현 방법

  • base를 1씩 늘려가면서 base의 N 제곱 값을 계산한다
  • 특정한 값 X에 base의 N 제곱값을 빼준다
  • 나머지가 음수면 0을 반환한다
  • 나머지가 0이면 1을 반환한다
  • 나머지가 0보다 클 경우, 나머지와 base + 1에 대해서 회귀함수를 재호출한다
  • X와 base + 1에 대해서 회귀함수를 재호출한다
  • 반환값을 모두 더해준다

function powerSum(X, N) {
    let base = 1;
    function calculateResume(value, base, exponent) {
       let resume = value - Math.pow(base, exponent);
       if (resume < 0) return 0;
       else if (resume === 0) return 1;
       else return calculateResume(resume, base + 1, exponent) + calculateResume(value, base + 1, exponent);
    }
    return calculateResume(X, base, N);
}