算法专题之链表(数据结构链表的经典算法)
前言
链表是一种物理存储结构上非连续的数据结构,数据的逻辑顺序是通过链表中的指针链接次序实现相互勾连.
链表相对数组而言有很多不同之处,在特定场景下能发挥独特的优势.
例如链表的插入和删除操作比数组效率高,数组需要改变其他元素的位置,而链表只需要改变指针的指向.
javascript中没有直接生成链表的api,但仍然可以利用语言本身的特性实现一条链表并完成其他操作.
链表的实现
链表的数据结构如下图,每一个节点都包含一条数据和指向下一个节点的索引.
如果获取了链表中的某一个节点,比如第一个节点,那么就可以获取节点的当前值1和下一个节点.通过下一个节点又可以拿到下下个节点.
因此一旦获取头部首节点,通过不断往后遍历是可以拿到链表上所有节点的值.头节点也可以称之为头指针.
代码实现
单个节点的代码实现非常简单(如下),每个节点都包含一个值value和指向下一个节点的索引next.
class Node {
constructor(value){
this.value = value;
this.next = null;
}
}
const node = new Node(1);
console.log(node); // { value: 1, next: null }复制代码链表是有一个个节点组成的,只要设置好节点与节点前后关系,就可以生成一条链表(代码如下).
class NodeList {
constructor(list){
const head = new Node(list.shift());
let parent = head;
list.forEach((value)=>{
parent.next = new Node(value);
parent = parent.next;
})
return head;
}
}
console.log(new NodeList([1,2,3,4])); // {"value":1,"next":{"value":2,"next":{"value":3,"next":{"value":4,"next":null}}}}复制代码通过类NodeList生成一条链表并返回头指针,let head = new NodeList([1,2,3,4]).
头指针head以遍历的形式能够获取链表上每个节点的值(代码如下).
while(head){
console.log(head.value); // 依次输出 1 2 3 4
head = head.next;
}复制代码链表相关算法
环形链表
普通单向链表,头指针遍历链表不断右移,最终会移动到空节点处结束遍历.
但环形链表用头指针遍历后,指针最终不会移动到空节点,而是陷入了死循环(如下图).
题目:判断一个链表是否有环?
实现思路:
判断一个链表是否有环,可以采用快慢指针的思想.快指针每次右移两格,慢指针右移一格.
两个指针同时从头部开始遍历链表,如果链表有环,快指针最终一定会追上慢指针.
代码实现
const head = new NodeList([1,2,3,4]);
head.next.next.next.next = head.next; // 手动改成环形链表
function isCircle(head){
let fast = head;
let slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if((fast && fast.next === slow) || fast === slow){
return true;
}
}
return false;
}
console.log(isCircle(head)); // true复制代码相交链表
两条链表相交后的样子如下图.
题目:判断两条链表是否相交,如果相交就返回相交的那个节点?
实现思路:
从上图观察,两条链表相交后,相交点后面的节点都是一样的.
因此存在两条长度不等的链表相交时,那么可以确定较长长度的那条链表所多出来的长度节点是绝对不会发生相交的.
例如图中(1,2,3,4,20,21,22)形成的长链表长度比另一条短链表长度多2.那么可以断定长链表前2个元素绝不会出现相交.
代码实现
const LinkOne = new NodeList([1,2,3,4,5]);
const LinkTwo = new NodeList([6,7]);
LinkTwo.next.next = LinkOne.next.next.next; // 让两条链表相交
function isCross(head_one,head_two){
let one_len = 1;
let two_len = 1;
let next_one = head_one;
let next_two = head_two;
while(next_one = next_one.next){
one_len++; //获取链表1的长度
}
while(next_two = next_two.next){
two_len++; //获取链表2的长度
}
const extra = Math.abs(one_len - two_len); //多余的长度
let long,short;
if(one_len >= two_len){ // 如果链表1比链表2长
long = head_one;
short = head_two;
}else{
long = head_two;
short = head_one;
}
for(let i = 0;i < extra;i++){ // 先排除掉多余的长度
long = long.next;
}
while(true){
if(!long.next){
return false; //不相交返回false
}
else if(long.next === short.next){
return long.next;
}else{
long = long.next;
short = short.next;
}
}
}
console.log(isCross(LinkOne,LinkTwo)); // { value: 4, next: Node { value: 5, next: null } }复制代码链表的反转
题目:如何实现链表的反转?
实现思路:
观察下图,(1,2,3,4,5)是一条链表,目标是翻转链表得到(5,4,3,2,1).
首先新建一个值为null的节点next,将右侧链表第一个节点1指向next节点,并将1节点赋值给next节点.
同理链表第二个节点2改成指向next节点,并将2节点赋值给next节点.遍历持续往下,最终实现了(5,4,3,2,1)链表的反转,最后next节点变成了头指针5节点.
代码实现
const head = new NodeList([1,2,3,4,5]);
function reverse(head){
let next = new Node(null);
while(head){
const tmp = head.next;
head.next = next;
next = head;
head = tmp;
}
return next;
}
console.log(reverse(head)); // {"value":5,"next":{"value":4,"next":{"value":3,"next":{"value":2,"next":{"value":1,"next":{"value":null,"next":null}}}}}}复制代码回文链表
回文的含义是指无论从前往后读还是从后往前读,当所读的顺序一致时,读取的值应该相等.
比如存在链表(1,2,3,2,1),从前往后读和从后往前获取的值是相同的,因此该链表为回文链表.
另外偶数链表(1,2,2,1)也符合回文链表的标准.
题目:判断一个链表是否为回文链表?
实现思路:
为了验证一个链表是否为回文链表,首先在链表头部设置两个指针:快指针fast和慢指针slow.
快慢指针同时遍历链表,快指针每次右移2格,慢指针右移1格.
因此快指针跑的距离是慢指针的两倍,当快指针跑到链表最后一个节点时,慢指针所处的位置恰好是链表的中心点(如下图).
此时只需要将中心点右侧的链表进行反转,再依次遍历同左侧链表的值进行一一比较,就能判断出链表是否为回文链表.
代码实现
const { reverse } = require("./reverse.js"); //上面介绍的链表反转函数
const head = new NodeList([1,2,3,2,1]);
function Palindrome(head){
let fast = head; // 创建快指针
let slow = head; // 创建慢指针
let start;
while(fast && fast.next){
fast = fast.next.next;;
slow = slow.next;
}
if(fast){ // 链表是奇数个
start = slow.next;
}else{ // 链表是偶数个
start = slow;
}
start = reverse(start); //使用上一小节介绍的翻转函数,将中心点右侧的链表反转
while(head != slow){
if(head.value !== start.value){
return false; // 有一个值不相等就不是回文链表
}
head = head.next;
start = start.next;
}
return true;
}
console.log(Palindrome(head)); //true复制代码链表的合并
存在两个有序链表(1,3,6,7,9)和(2,3,6),期待合并成一个有序链表(1,2,3,3,6,6,7,9)输出.
题目:如何合并两条有序链表?
实现思路:
观察下图.创建一个空节点next,以及两个头指针head1和head2.
两条链表使用头指针同时遍历,当head1的值比head2的值小时,就将next节点指向head1.指针head1和节点next都右移一位.
第二轮再将head1的值与head2的值比较,发现head2的值比head1的值小,于是将next节点指向head2,指针head2和节点next都右移一位.
依此类推,不断比较两条链表的值,将较小的值的节点接到next节点后面,最终由next节点推动生成的链表便是最终按序排列的合成链表.
代码实现
const head1 = new NodeList([1,3,6,7,9]);
const head2 = new NodeList([2,3,6]);
function Merge(head1,head2){
const start = new Node(null); // 创建一个空节点
let next = start;
while(head1 && head2){
if(head1.value <= head2.value){
next.next = head1;
next = head1;
head1 = head1.next;
}else{
next.next = head2;
next = head2;
head2 = head2.next;
}
}
const extra = head1?head1:head2; // 长一些链表的剩余部分
next.next = extra;
return start.next;
}
console.log(Merge(head1,head2)); // {"value":1,"next":{"value":2,"next":{"value":3,"next":{"value":3,"next":{"value":6,"next":{"value":6,"next":{"value":7,"next":{"value":9,"next":null}}}}}}}}复制代码链表的排序
题目:使用快排将一条链表的值按从小到大的顺序排列?
实现思路:
快速排序的原理通常取队列第一个值作为基准值,然后遍历整个队列,将小于基准值的数放左边,大于基准值的数放右边.然后将基准值左边和右边的子队列分别递归执行上一流程.
链表实现快拍具体步骤如下(观察下图),定义两个指针smaller和bigger.将链表的第一个节点anchor设定为快速排序的基准点.
首先比较bigger与anchor的值,bigger的值大,不做任何操作指针右移一位,继续比较bigger与anchor的值.
bigger的值为2,小于anchor.将smaller指针右移一位,用smaller的值和bigger的值进行交换,此时链表变成(3,2,9,1,6).
交换后bigger指针右移一位再与anchor的值比较,此时bigger的值为1小于anchor,smaller指针右移一位再与bigger进行值交换,此时链表变成(3,2,1,9,6).
交换后bigger指针右移一位再与anchor的值比较,bigger的值大不做操作.
遍历结束,将anchor的值与smaller值进行交换,链表变成(1,2,3,9,6).
第一轮遍历后成功的将小于3的节点都放到了左边,大于3的节点放到了右边.剩下的任务是将3左边的子链表和右边的子链表分别递归执行上述步骤,直至将所有顺序排列完成.
代码实现
// 链表的排序
const head = new NodeList([3,9,2,4,6,5,3,1,7,8]);
function sort(head,tail){
if(head === tail){
return head;
}
let smaller = head;
let anchor = head;
let bigger = head.next;
while(bigger != tail){
if(bigger.value <= anchor.value){
smaller = smaller.next;
swap(smaller,bigger);
}
bigger = bigger.next;
}
swap(anchor,smaller);
sort(head,smaller);
sort(smaller.next,tail);
return head;
}
function swap(node_one,node_two){
const tmp = node_one.value;
node_one.value = node_two.value;
node_two.value = tmp;
}
console.log(sort(head,null)); // {"value":1,"next":{"value":2,"next":{"value":3,"next":{"value":
作者：Kay_
链接：https://juejin.cn/post/7032578799342616589