https://xin-tan.com/passages/2019-06-23-algorithm-offer/

二维数组里的查询

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var findNumberIn2DArray = function(matrix, target) {
    if(matrix === null || matrix.length < 1 || matrix[0].length < 1) {
        return false
    }
    //起点在右上角
    let row = 0, col = matrix[0].length-1
     //判断当前数组元素和target，如果当前大于target，往左走；小与target，往下走
    while (row < matrix.length && col >= 0) {
        if (matrix[row][col] === target) {
            return true
        } else if (matrix[row][col] > target) {
            col -= 1
        } else if (matrix[row][col] < target) {
            row += 1
        }
    }
     //走出边界了还没找到，说明不存在，返回false
    return false
};

逆序打印链表

考察点：用栈

var reversePrint = function(head) {
    let arr = []
    while(head) {
        arr.unshift(head.val)
        head = head.next
    }
    return arr
};

翻转链表

1-2-3-4-null
pre -> null current->head next
剑指offer - 图1
注意移动pre 和 current
退出条件是current != null
退出时current === null
所以应该返回prev， prev才是链表头结点

var reverseList = function(head) {
    let prev = null, current = head, next = head
    while(current) {
        next = current.next
        current.next = prev
        prev = current
        current = next
    }
    return prev
};

复制链表

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */
/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
    // 判断如果是空链表
    if (!head) return null
    let node = new Node(),temp = node,map = new Map()
    let curr = head
    // 第一次循环，赋值和存map
    while (curr) {
        temp.val = curr.val
        temp.next = curr.next ? new Node() : null
        map.set(curr, temp)
        curr = curr.next
        temp = temp.next
    }
    // 临时节点重新指向头节点
    curr = head
    temp = node
    // 走第二次，处理random
    while (curr) {
        temp.random = map.get(curr.random) 
        temp = temp.next
        curr = curr.next
    }
    return node
};

需要注意的是：中间需要回到头结点，所以在最开始创建temp时还用了另外一个变量node，同时保存地址
找random里这一句是灵魂

temp.random = map.get(curr.random)

备注 2020年6月27日递归(1)_00.png 备注 2020年6月27日递归(1)_01.png

判断一个链表是否有环

需要注意的是 slow 和 head的起始点不一样

var hasCycle = function(head) {
    let slow = head.next
    let fast = head
    while(fast !== null && fast.next !== null ) {
         if (fast.val === slow.val) {
            return true
        } 
        fast = fast.next.next
        slow = slow.next    
    }
    return false
};

也可以用set

var hasCycle = function(head) {
    let nodeSet = new Set()
    while(head){
        if (nodeSet.has(head)) {
            return true
        }
        nodeSet.add(head)
        head = head.next
    }
    return false
};

删除链表里的全部重复元素

1-1-2-2-3-4 得到3-4
思路：
参考题解：
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/solution/san-chong-jie-fa-duo-tu-zhan-shi-82-shan-chu-pai-x/
这里我们使用双指针的方式，定义a，b两个指针。
考虑到一些边界条件，比如1->1->1->2这种情况，需要把开头的几个1给去掉，我们增加一个哑结点，方便边界处理。

初始的两个指针如下:

将a指针指向哑结点
将b指针指向head(哑结点的下一个节点)

如果a指向的值不等于b指向的值，则两个指针都前进一位
否则，就单独移动b，b不断往前走，直到a指向的值不等于b指向的值。

注意，这里不是直接比较a.val==b.val，这么比较不对，因为初始的时候，a指向的是哑结点，所以比较逻辑应该是这样：

a.next.val === b.next.val

当两个指针指向的值相等时，b不断往前移动，这里是通过一个while循环判断的，因为要过滤掉1->2->2->2->3重复的2。
那么整个逻辑就是两个while，但时间复杂度不是O(N^2)，而是O(N)，空间上也只是常数级别。

var deleteDuplicates = function(head) {
    if(head === null || head.next === null) {
        return head
    }
    let dummyNode = new ListNode(0)
    dummyNode.next = head
    let a = dummyNode, b = head
    while(a.next!== null && b.next!== null) {
        if (a.next.val !== b.next.val) {
            a = a.next
            b = b.next
        } else {
            while(b.next !== null) {
                if (a.next.val !== b.next.val) {
                    break;
                }
                b = b.next
            }
            a.next = b.next
            b = b.next
        }
    }
    return dummyNode.next
};

相交链表

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/tu-jie-xiang-jiao-lian-biao-by-user7208t/

var getIntersectionNode = function(headA, headB) {
    if (headA === null || headB === null) {
        return null
    }
    let pA = headA, pB = headB
    while(pA !== pB) {
        pA = pA===null? headB : pA.next
        pB = pB===null? headA:pB.next
    }
    return pA
};

合并两个排序的链表

这道题可以使用递归实现，新链表也不需要构造新节点，我们下面列举递归三个要素
终止条件：两条链表分别名为 l1 和 l2，当 l1 为空或 l2 为空时结束
返回值：每一层调用都返回排序好的链表头
本级递归内容：如果 l1 的 val 值更小，则将 l1.next 与排序好的链表头相接，l2 同理
O(m+n)O(m+n)，mm 为 l1的长度，nn 为 l2 的长度

https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/hua-jie-suan-fa-21-he-bing-liang-ge-you-xu-lian-bi/

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

https://leetcode-cn.com/problems/copy-list-with-random-pointer/

https://github.com/ConardLi/awesome-coding-js/blob/master/%E5%89%91%E6%8C%87offer/1.%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84%E6%9F%A5%E6%89%BE.md

http://www.conardli.top/docs/dataStructure/%E9%93%BE%E8%A1%A8/%E5%A4%8D%E6%9D%82%E9%93%BE%E8%A1%A8%E7%9A%84%E5%A4%8D%E5%88%B6.html#%E4%BB%A3%E7%A0%81

https://github.com/YaxeZhang/Just-Code