关于javascript:JS链表与算法题浅析

JS-链表与算法-Linked list

一、什么是链表

[维基百科] 链表（Linked list）是一种常见的根底数据结构，是一种线性表，然而并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

二、链表分类

链表常见的有 3 类：单链表、双向链表、循环链表。

三、链表设计

说到链表，就要提下数组，个别链表都是和数组进行比照。

在很多编程语言中，数组的长度时固定的，所以数组中的减少和删除比拟麻烦，须要频繁的挪动数组中的其余元素。
然而，JavaScript中的数组并不存在上述问题，JS中的数组绝对其余语言应用上更不便，因为JS中的数组实质是一个相似数组的对象，这就使得JS的数组尽管应用更不便，但比其余语言(C++、Java、C#)的数组效率要低。

所以，在理论利用中如果发现数组很慢，就能够思考应用链表来代替它。除了对数据的随机拜访，链表简直能够用在任何能够应用一维数组的状况中。如果须要随机拜访，数组依然是更好的抉择。

定义

// 定义var a = { val: 'a' };var b = { val: 'b' };var c = { val: 'c' };var d = { val: 'd' };a.next = b;b.next = c;c.next = d;// 遍历var point = a;while (point) {    console.log(point.val);    point = point.next;}

插入

// 插入var e = { val: e };c.next = e;e.next = d;

// 删除c.next = d;

数据结构

// Definition for singly-linked list. 定义单链表function ListNode(val) {    this.val = val;    this.next = null;}

四、链表练习

1、删除链表中的指定节点

(题目来自力扣第237题)

题目形容：请编写一个函数，使其能够删除某个链表中给定的（非开端）节点。传入函数的惟一参数为 要被删除的节点 。

示例 1：

输出： 4->5->1->9, val = 5
输入： 4->1->9

示例 2：

输出： 4->5->1->9, val = 1
输入： 4->5->9

提醒：

链表至多蕴含两个节点
链表中所有节点的值都是惟一的
给定的节点为非开端节点，并且肯定是链表中的一个无效节点
不要从你的函数中返回任何后果

/** * 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) {};

题目初始化

// 初始化function ListNode(val){    this.val = val;    this.next = null;}// 4->5->1->9var node1 = new ListNode(4);var node2 = new ListNode(5);var node3 = new ListNode(1);var node4 = new ListNode(9);node1.next = node2;node2.next = node3;node3.next = node4;

题解:

解题思路：
1、无奈间接获取被删除节点的上个节点；
2、将被删除节点转移到下个节点。

code view:

var deleteNode = function(node) {    node.val = node.next.val;    node.next = node.next.next;};deleteNode(node2);console.log(node1);

2、删除链表中的反复元素

(题目来自力扣第83题)

题目形容：给定一个排序链表，删除所有反复的元素，使得每个元素只呈现一次。

示例 1：

输出： 1->1->2
输入： 1->2

示例 2：

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

/** * Definition for singly-linked list. * function ListNode(val) { *     this.val = val; *     this.next = null; * } *//** * @param {ListNode} head * @return {ListNode} */var reverseList = function(head) {};

题目初始化

// 初始化function ListNode(val){    this.val = val;    this.next = null;}// 1->1->2var node1 = new ListNode(1);node1.next = new ListNode(1);node1.next.next = new ListNode(2);// 1->1->2->3->3var node2 = new ListNode(1);node2.next = new ListNode(1);node2.next.next = new ListNode(2);node2.next.next.next = new ListNode(3);node2.next.next.next.next = new ListNode(3);

题解:

解题思路：
1、因为链表是有序的，所以反复元素肯定相邻；
2、遍历链表，如果发现以后元素和下个元素的值相等，就删除下个元素。

code view:

/** * @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 {            p = p.next; // 只有不相等时指针才指向下一个元素，防止出现多个        }    }    return head;};deleteDuplicates(node1);console.log(node1);deleteDuplicates(node2);console.log(node2);

3、反转链表

(题目来自力扣第206题)

题目形容：反转一个单链表。

示例 1：

输出： 1->2->3->4->5->NULL
输入： 5->4->3->2->1->NULL

/** * Definition for singly-linked list. * function ListNode(val) { *     this.val = val; *     this.next = null; * } *//** * @param {ListNode} head * @return {ListNode} */var reverseList = function(head) {};

题目初始化

// 初始化function ListNode(val){    this.val = val;    this.next = null;}// 1->1->2var node = new ListNode(1);node.next = new ListNode(2);node.next.next = new ListNode(3);node.next.next.next = new ListNode(4);node.next.next.next.next = new ListNode(5);

题解:

解题思路：
1、反转两个节点：将n+1的next指向n；
输出: n -> n+1
输入: n+1 -> n
2、反转多个节点：双指针遍历链表，反复上述操作。
输出： 1->2->3->4->5->NULL
输入： 5->4->3->2->1->NULL

code view:

/** * @param {ListNode} head * @return {ListNode} */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;};reverseList(node);console.log(reverseList);

4、判断环形链表

(题目来自力扣第141题)

题目形容：给定一个链表，判断链表中是否有环。
如果链表中有某个节点，能够通过间断跟踪 next 指针再次达到，则链表中存在环。为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。留神：pos 不作为参数进行传递，仅仅是为了标识链表的理论状况。

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

示例 1：

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

示例 2：

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

示例 3：

输出： head = [1], pos = -1
输入： false
解释：链表中没有环。

提醒：

链表中节点的数目范畴是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个无效索引

/** * Definition for singly-linked list. * function ListNode(val) { *     this.val = val; *     this.next = null; * } *//** * @param {ListNode} head * @return {boolean} */var hasCycle = function(head) {  };

题目初始化

// 初始化function ListNode(val){    this.val = val;    this.next = null;}// 3->2->0->4var node1 = new ListNode(3);var node2 = new ListNode(2);var node3 = new ListNode(0);var node4 = new ListNode(4);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node2;// 1->2var node5 = new ListNode(1);var node6 = new ListNode(2);node5.next = node6;node6.next = node5;// 1var node7 = new ListNode(1);

题解:

解题思路：
1、两个人在圆形操场上的同一个终点起跑，速度快的人和速度慢的人肯定会再次相遇（起码超过一圈）；
2、用一快一慢两个指针遍历链表，如果指针可能相逢，那么链表就有圈。

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

code view:

/** * @param {ListNode} head * @return {boolean} */var hasCycle = function(head) {    var p1 = head;    var p2 = head;    while(p1 && p2 && p2.next) {        p1 = p1.next;        p2 = p2.next.next;        if (p1 === p2) {            return true;        }    }    return false;};

5、链表的两头结点

(题目来自力扣第876题)

题目形容：给定一个头结点为 head 的非空单链表，返回链表的两头结点。

如果有两个两头结点，则返回第二个两头结点。

示例 1：

输出：[1,2,3,4,5]
输入：此列表中的结点 3 (序列化模式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
留神，咱们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输出：[1,2,3,4,5,6]
输入：此列表中的结点 4 (序列化模式：[4,5,6])
因为该列表有两个两头结点，值别离为 3 和 4，咱们返回第二个结点。

/** * Definition for singly-linked list. * function ListNode(val) { *     this.val = val; *     this.next = null; * } *//** * @param {ListNode} head * @return {ListNode} */var middleNode = function(head) {};

题目初始化

// 初始化function ListNode(val){    this.val = val;    this.next = null;}// l1: 1->2->3->4->5var l1 = new ListNode(1);l1.next = new ListNode(2);l1.next.next = new ListNode(3);l1.next.next.next = new ListNode(4);l1.next.next.next.next = new ListNode(5);// l2: 1->2->3->4->5var l2 = new ListNode(1);l2.next = new ListNode(2);l2.next.next = new ListNode(3);l2.next.next.next = new ListNode(4);l2.next.next.next.next = new ListNode(5);l2.next.next.next.next.next  = new ListNode(6);// l3: 1var l3 = new ListNode(1);

题解:

解题思路：
1、快指针p每次移2节点，慢指针head移1节点
2、快指针先到尾，此时慢指针的地位刚好在两头

code view:

/** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */var middleNode = function(head) {    var p = head;    while(p && p.next) {        head = head.next;        p = p.next.next;    }    return head;};

6、链表相加

(题目来自力扣第2题)

题目形容：给出两个非空的链表用来示意两个非负的整数。其中，它们各自的位数是依照逆序的形式存储的，并且它们的每个节点只能存储一位数字。

如果，咱们将这两个数相加起来，则会返回一个新的链表来示意它们的和。

您能够假如除了数字 0 之外，这两个数都不会以 0 结尾。

示例 1：

输出：(1 -> 4 -> 3) + (5 -> 6 -> 4)
输入：6 -> 0 -> 8
起因：341 + 465 = 806

/** * 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) {};

题目初始化

// 初始化function ListNode(val){    this.val = val;    this.next = null;}// l1: 1->4->3var l1 = new ListNode(1);l1.next = new ListNode(4);l1.next.next = new ListNode(3);// l2: 5->6->4var l2 = new ListNode(5);l2.next = new ListNode(6);l2.next.next = new ListNode(4);// l3: 1var l3 = new ListNode(1);// l4: 1->6->9var l4 = new ListNode(1);l4.next = new ListNode(6);l4.next.next = new ListNode(9);

题解:

解题思路：
1、新建一个空链表
2、遍历被相加的两个链表，模仿相加的操作，将相加后后果的个位数追加到新链表上，将十位数留到下一位去相加

code view:

/** * @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 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;};

五、JS中的原型链

原型链的实质是链表
原型链上的节点是各种原型对象，比方Function.prototype 、Object.prototype、Array.prototype ...
原型链通过 __proto__ 属性连贯各种原型对象

参考资料：
维基百科---链表
JS数据结构第二篇---链表
数据结构：链表