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->9
var 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->2
var node1 = new ListNode(1);
node1.next = new ListNode(1);
node1.next.next = new ListNode(2);
// 1->1->2->3->3
var 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->2
var 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->4
var 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->2
var node5 = new ListNode(1);
var node6 = new ListNode(2);
node5.next = node6;
node6.next = node5;
// 1
var 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->5
var 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->5
var 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: 1
var 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->3
var l1 = new ListNode(1);
l1.next = new ListNode(4);
l1.next.next = new ListNode(3);
// l2: 5->6->4
var l2 = new ListNode(5);
l2.next = new ListNode(6);
l2.next.next = new ListNode(4);
// l3: 1
var l3 = new ListNode(1);
// l4: 1->6->9
var 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 数据结构第二篇 — 链表
数据结构:链表