链表 - 《算法》 - 极客文档

数组与链表的区别
206 反转链表
- 栈解
2 两数相加
83 删除排序链表中的重复元素
141 环形链表
JS中的原型链
使用链表指针获取JSON的节点值

多个元素组成的列表
元素存储不连续，用next指针连在一起。

数组与链表的区别

数组：增删非首尾元素时，往往需要移动元素。
链表：增删非首尾元素，不需要移动元素，只需要更改next指向即可。

js中的链表。

js中没有链表的数据结构。
可以用Object模拟链表。 ```javascript 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; while(p) { console.log(p.val) p = p.next; }

//插入元素 const e = { val: ‘e’} c.next = e; e.next = d;

//删除 c.next = d;


<a name="HyNkb"></a>
## 237.删除链表中的节点
4 ---> 5  ---> 1 ---> 9<br />解题思路：
- 无法直接获取被删除节点的上个节点。
- 将被删除节点转移到下个节点。
解题步骤：
- 将被删除节点的值改为下个节点的值
- 删除下个节点
```javascript
var deleteNode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
}

时间复杂度O(1)，空间复杂度O(1)。

206 反转链表

1 -> 2 ->3 -> 4 -> 5 -> NULL
5 -> 4 -> 3 -> 2 -> 1 -> NULL

解题思路：

反转两个节点：将n+1的next指向n
反转多个节点：是指针遍历链表，重复上述操作

双指针：一个指针指向2，一个指针指向1.

解题步骤：

双指针一前一后遍历链表。
反转双指针。

先用临时变量保存需要反转链表的next,当前链表的下一个指向另一个链表，另一个链表等于当前反转链表。然后将当前反转链表的所在位置指向临时变量。

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;
}


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

链表 - 图3
leetcode解法

栈解

思路

既然是反转，那么符合栈先进后出的特点
将原节点依次入栈
出栈时，重新构造链表改变指向

同样设置哨兵节点

最后返回哨兵的next即为所求

var reverseList = function(head) {
let tmp = head;
let tHead = new ListNode(0);
let pre = tHead;
let stack = [];
while(tmp){
stack.push(tmp.val);
tmp = tmp.next;
}
while(stack.length != 0){
pre.next = new ListNode(stack.pop());
pre = pre.next;
}
return tHead.next;
};

2 两数相加

输入：（ 2 —> 4 —> 3）+ (5 —> 6 —> 4)
输出： 7 —> 0 —>8
原因：342 + 465 = 807
解题思路：

小学数学题，模拟相加操作。
需要遍历链表

解题步骤：

新建一个空链表

遍历被相加的两个链表，模拟相加操作，将个位数追加到新链表上，将十位数留到下一位去相加。

var addTwoNumbers = function(l1,l2) {
  const l3 = new ListNode(0);
  let p1 = l1;
  let p2 = l2;
  let p3 = l3;
  let carry = 0;

  while(p1 || p2) {
      const v1 = p1 ? p1.val : 0;
      const v2 = p2 ? p2.val : 0;
      const val = v1 + v2 + carry;
      carry = Math.floor(val / 10);
      p3.next = new ListNode(val % 10);
      if(p1) p1 = p1.next;
      if(p2) p2 = p2.next;
      p3 = p3.next;
  }

  if(carry) {
      p3.next = new ListNode(carry)
  }
  return l3.next
}

83 删除排序链表中的重复元素

输入： 1 —> 1 —> 1 —> 2
输出： 1 —> 2
解题思路：

因为链表是有序的，所以重复元素一定相邻。
遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值。

解题步骤：

遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值。

遍历结束后，返回原链表的头部。（因为是在原链表上进行删除操作，所以这里我们直接返回原链表）。

/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function(head) {
  let p = head;
  while(p && p.next) {
      if(p.val === p.next.val) {
          p.next = p.next.next;
      }else {
          //让链表继续往下执行,相等的情况继续执行上面的if语句
          p = p.next
      }
  }
  return head
};

时间复杂度：O(n);
空间复杂度：O(1);

141 环形链表

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

链表 - 图4

解题思路：

两个人在圆形操场上的起点同时起跑，速度快的人一定会超过速度慢的人一圈。
用一快一慢两个指针遍历链表，如果指针能够相逢，那么链表就有圈。

解题步骤：

用一快一慢两个指针遍历链表，如果指针能够相逢，就返回true。
遍历结束后，还没有相逢就返回false。

时间复杂度：O(n)
空间复杂度：O(1)

var hasCycle = function(head) {
    let p1 = head;
    let p2 = head;

    while(p1 && p2 && p2.next) {
        p1 = p1.next;
        p2 = p2.next.next;
        if(p1 === p2) {
            return true
        }
    }
    return false;
};

JS中的原型链

原型链的本质是链表。
原型链上的节点是各种原型对象，比如：Function.prototype、Object.prototype。。。
原型链通过proto属性连接各种原型对象。

原型链长什么样？

obj ->Object.prototype -> null
func -> Function.prototype -> Object.prototype -> null
arr-> Array.prototype -> Object.prototype -> null

obj.__proto__ === Object.prototype  //true

obj.__proto__.__proto__ === null //true

func.__proto__ === Function.prototype  //true

func.__proto__ === Object.prototype  //false

func.__proto__.__proto__ === Object.prototype //true

func.__proto__.__proto__.__proto__ === null //true

//array同理

func instanceof Object //true

如果A沿着原型链能找到B.prototype,那么A instanceof B 为 true
如果在A对象上没有找到x属性，那么会沿着原型链找x属性。

面试题：
instanceof原理，并且用代码实现？

知识点：如果A沿着原型链能找到B.prototype,那么A instanceof B 为 true
解法：遍历A的原型链，如果找到B.prototype,返回为true,否则返回false。

const instanceOf = (A, B) => {
    let p = A;
    while(p) {
        if( p === B.prototype) {
            return true;
        }
        p = p.__proto__;
    }

    return false;
};

面试题2：

var foo = {},
    F = function() {};
Object.prototype.a = 'value a';
Function.prototype.b = 'value b';

foo.a //'value a'
foo.b // undefined
F.a  // 'value a'
F.b //'value b'

使用链表指针获取JSON的节点值

const json = {
    a: { b: {c:1}},
    d: {e:2},
}

const path = ['a', 'b', 'c'];
let p = json;
path.forEach(k=>{
    p = p[k]
})

Object.prototype