分类： Algorithm

示例：
1->2->3->4->5->null
5->4->3->2->1->null

js中模拟链表

const a = { val: 'a' }
const b = { val: 'b' }
const c = { val: 'c' }
const d = { val: 'd' }
a.next = b
b.next = c
c.next = d

//遍历链表
let p = a //point
while (p) {
    console.log(p.val)
    p = p.next
}

// 插入一个e节点
const e = { val: 'e' }
c.next = e
e.next = d

// 删除e节点
c.next = d

 

解题思路：
1. 先思考如何反转2个节点，将n+1的next指向n
2. 双指针遍历链表，然后重复上面的动作

解题步骤：
1. 双指针遍历
2. 反转双指针

var reverseList = function (head) {
    let p1 = head
    let p2 = null
    while (p1) {
        const tmp = p1.next
        p1.next = p2
        p2 = p1
        p1 = tmp
    }
    return p2
};

题目：例如这样一个[1,3,4,5,7]有序的数组，如何快速找到某个值的下标？
这是一个经典的二分查找算法题。

解题思路：

1. 先找到数组的中间下标值
2. 然后判断目标值如果大于中间值，就在数组的右半边继续查找
3. 如果目标值小于中间值，就在数组的左半边继续查找
4. 然后不断的重复上面的步骤。

时间复杂度是O(logN) 因为遍历减半了就是n的一半=logN，如果遍历了全部就是N

let binarySeach = function (arr, target) {
    let s = 0 // 开始下标
    let e = arr.length - 1 //结束下标
    while (s <= e) { // 如果开始下标小于等于结束下标就标识区间内有值
        let mid = Math.floor((s + e) / 2) //当前数组的中间值下标
        let item = arr[mid] // 中间值
        if (item < target) { //如果中间的值小于目标值
            s = mid + 1 // 把开始下标移动到中间值的后面，在2叉树的右边继续搜索了
        } else if (item > target) { //如果中间值大于目标值
            e = mid - 1 // 把结束下标移动到中间值的前面一位，在2叉树的左边数组继续搜索
        } else { // 如果中间值等于目标值直接返回当前下标
            return mid
        }
    }
    return -1 // 找不到就返回-1
}
let res = binarySeach([1, 2, 3, 4, 5], 2)
console.log(res)

问题：一个值未知的数组，如何快速根据值的大小进行排序。
思路：
先找到数组的中位数pivot作为参照物
遍历数组中的每一项与其比较，然后小的放到一个Left的空数组里面，比它大的放点right的空数组里面
再递归左边的数组和右边的组数，最后把2个数组和中位数连接到一个数组里面去

let arr = [11, 82, 4, 44, 20]
var quickSort = function (arr) {
    if (arr.length <= 1) { return arr }
    var pivotIndex = Math.floor(arr.length / 2)
    var pivot = arr.splice(pivotIndex, 1)[0]
    var left = []
    var right = []
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return quickSort(left).concat([pivot], quickSort(right))
}
console.info(quickSort(arr))

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
例如：
给定 nums = [2, 7, 11, 15], target = 9 。 ·8
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路：
1. 把nums想象成相亲者
2. 把target想象成匹配条件
3. 用字典建立一个婚姻介绍所，存储相亲者的数字和下标

解题步骤：
新建一个字典作为婚姻介绍所
遍历nums里的值，有合适的就牵手成功，没有就先登记，字典里面Key就是nums里的值，value就是下标。

var twoSum = function (nums, target) {
    let map = new Map() // 婚姻介绍所
    for (let i = 0; i < nums.length; i++) {
        const n = nums[i] //自己
        const n2 = target - n //对象
        if (map.has(n2)) { //是否有合适的对象
            return [map.get(n2), i] //有就返回对象的下标和自己的下标
        } else {
            map.set(n, i) // 没有合适的对象就把自己登记到介绍所
        }
    }
}
let res = twoSum([2, 7, 11, 15], 9)