算法打卡-leetcode-20210406

1. 汉诺塔问题
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。

经典汉诺塔问题，我还在默默计算当圆盘都在B柱时如何将盘子移回A柱，想了好久，实在想不出一个有规律的解法，就看了题解，结果推荐题解是直接把A柱和B柱的门牌号给换了，难怪评级只有简单。。。
递归的经典问题与解答，没有什么好讲的了。

/**
 * @param {number[]} A
 * @param {number[]} B
 * @param {number[]} C
 * @return {void} Do not return anything, modify C in-place instead.
 */
var hanota = function (A, B, C) {
    function move(length, A, B, C) {
        if (length === 1) {
            C.push(A.pop());
        } else {
            move(length - 1, A, C, B);
            C.push(A.pop());
            move(length - 1, B, A, C);
        }
    }

    move(A.length, A, B, C);
};

2. 排序链表 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶： 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

目前常用的算法里面，只有快排和归并排序时间复杂度是O(n log n)，我选择了归并排序，因为在链表我这一生之敌面前，归并排序的思想好理解一些。 重点就是快慢指针的定义，和合并算法的编写，也是递归思想，没啥好说的。

/**
 * 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}
 */
var sortList = function(head) {
    function sortList(head){
        if(head == null || head.next == null){
            return head;
        }
        let fast = head;
        let slow = head;
        while(fast.next != null && fast.next.next != null ){
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = slow;
        slow = slow.next;
        fast.next = null;
        fast = sortList(head);
        slow = sortList(slow);
        
        return merga(fast, slow);
    }

    function merga(head1, head2){
        if(head1 == null){
            return head2;
        }
        if(head2 == null){
            return head1;
        }
        let result, p;
        if(head1.val > head2.val){
            result = head2;
            head2 = head2.next;
        } else {
            result = head1;
            head1 = head1.next;
        }
        p = result;
        while(head1 != null && head2 != null){
            if(head1.val > head2.val){
                p.next = head2;
                head2 = head2.next;
            } else {
                p.next = head1;
                head1 = head1.next;
            }
            p = p.next;
        }
        if(head1 != null){
            p.next = head1;
        } else if(head2 != null){
            p.next = head2;
        }
        return result;
    }

    return sortList(head);
};