note

# 定义

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

# 数组 vs 链表

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

# 基本用法

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: 'd' }
c.next = e
e.next = d

// 删除
c.next = d

# 使用场景

# 算法题：删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为要被删除的节点。

https://leetcode-cn.com/problems/delete-node-in-a-linked-list/

  • 解题思路：如果无法直接获取被删除节点的上个节点（如果直接找到上个节点，可以将上个节点的 next 指针指向被删除节点的 next），可以将被删除节点转移到下个节点。
  1. 将被删除节点的值改为下个节点的值。
  2. 直接删除下个节点。
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
  node.val = node.next.val
  node.next = node.next.next
}

# 算法题：反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

  • 示例：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
  • 解题思路：反转两个节点：将 n + 1 的 next 指向 n；反转多个节点：双指针遍历链表，重复上述操作。
  • 解题步骤：双指针一前一后遍历链表，然后进行反转双指针。

https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

  • 代码：
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;
};

# 算法题：两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

链接：https://leetcode-cn.com/problems/add-two-numbers

  • 解题思路：就是简单的数学相加操作，需要用到遍历链表进行操作。

  • 解题步骤：新建一个空链表作为最后结果输出链表，遍历被相加的两个链表，模拟相加操作；将个位数追加到新链表上，将十位数留到下一位去相加。

  • 代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
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 add = v1 + v2 + carry;
        carry = Math.floor(add / 10);

        // 获取个位上的数值
        p3.next = new ListNode(add % 10);
        if (p1) p1 = p1.next;
        if (p2) p2 = p2.next;
        p3 = p3.next;
    }
    if (carry) {
        p3.next = new ListNode(carry);
    }
    return l3.next;
};

# 算法题：删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例：

输入: 1->1->2
输出: 1->2

输入: 1->1->2->3->3
输出: 1->2->3

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

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

  • 代码：

var deleteDuplicates = function(head) {
    let p = head;
    while(p && p.next) {
        if (p.val === p.next.val) {
            p.next = p.next.next;
        } else {
          p = p.next;
        }
    }
    return head
};

# 算法题：环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

链接：https://leetcode-cn.com/problems/linked-list-cycle

  • 解题思路：用一快一慢两个指针遍历链表，如果指针能够相逢，那么链表就有环。

  • 代码：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
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
};

# 算法题：相交链表

编写一个程序，找到两个单链表相交的起始节点。

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    if (!headA || !headB ) { return; }
    let p1 = headA;
    let p2 = headB;
    while(p1 !== p2) {
        p1 = (p1 === null ? headB : p1.next);
        p2 = (p2 === null ? headA : p2.next);
    }
    return p1;
};

# JavaScript 中的原型链

  • 原型链的本质是链表
  • 原型链上的接地那是各种原型对象，比如：Function.prototype、Object.prototype
  • 原型链通过 __proto__ 属性连接各种原型对象（相当于 next 指针）

实现 instanceof 操作符：

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

const res = instanceOf([], Array)
const res1 = instanceOf(obj, Object)
const res2 = instanceOf([], Object)
console.log(res, res1, res2)

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

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

const path = ['a', 'b', 'c']

let p = json
path.forEach(k => {
  p = p[k]
})

console.log(p)
阅读量：

评 论：

更新: 12/17/2020, 5:13:59 PM

← 集合 →