处理链表的本质，是处理链表结点之间的指针关系
最近在看数据结构和算法，努力总结出道~
TL;DR
- JS里，链表就是嵌套的对象，
{val:1,next:{val:2,next:...}} - 链表里的指针，听起来很抽象，其实就是部分链表，依旧是嵌套对象，p是
{val:1,next:{val:2,next:...}} - 指针往后挪动，其实就是
p = p.next，也就是p变成{val:2,next:...} - 链表的最后一个节点，
next肯定是空的 - 处理链表的时候，一般为了边界问题，很多时候先创建一个空节点，指向链表，有备无患吧
基础：JS 怎么表示链表
JS 里，是没有链表这种数据类型的，所以用对象去表达链表
// 链表的节点类 function ListNode(val) { this.val = val; this.next = null; }
如果一个链表是1->2->4，JS 的表达方式
{ val:1, next:{ val:2, next:{ val:4, next:null } } }
网络异常，图片无法展示
|
基础：遍历一个链表
遍历链表的是时候，往往借助指针，指针往后挪，挪到空的时候就遍历完了
function walkList(list) { // 先指向第一个节点 let p = list; while (p) { // 打印当前指针对应结点的值 console.log(p.val); // 指针往后移动 p = p.next; } // p为空的时候，就是遍历完了 console.log("遍历完了"); }
增加一个节点
那1->2->4来说，如果想增加一个节点，变成1->2->3->4新增的节点 3 的 next 指针指向 4，2 的 next 指针指向 3
// 先创建新节点 const newNode = new ListNode(3); // 找到新节点前一个节点的指针，也就是这个指针指向2节点 const p2 = list1.next; // 找到新节点后一个节点的指针，也就是这个指针指向4节点 const p4 = p2.next; // 新节点的next指向 后一个节点的指针 newNode.next = p4; // 新节点的前一个指针，指向新节点 p2.next = newNode;
删除一个节点
那1->2->4来说，如果想删除一个节点，变成1->41 的节点直接指向 4 就好了
// 这里注意，防止删除的时候最后一个节点 p1.next = p1.next.next ? p1.next.next :null;
基础：新建一个链表
新建一个链表1->2，作为边界处理，一般会有一个空值的头结点
// 新节点 const n1 = new ListNode(1) const n2 = new ListNode(2) // 作为边界处理，会习惯性的将第一个节点的值置为空 // 为了后期知道首节点的引用，所以必须有个head指针 let head = new ListNode(); // 新链表的指针，这里p是指针，会移动 let p = head p.next = n1 // 指针移动 p = p.next // 链表加长 p.next = n2 // 指针移动 p = p.next const newList = head.next
练习：合并链表
网络异常，图片无法展示
|
- 新建链表
- 链表 1 和链表 2 各一个指针，遍历
- 比大小，然后放到新链表里
可以想象成每个节点都是扣子，新链表的指针像线一样，将扣子穿起来。
function ListNode(val, next) { this.val = val; this.next = null; } function mergeTwoLists(l1, l2) { let p1 = l1; let p2 = l2; // 首个空节点用来规避边界问题，引用必须保存 let head = new ListNode(); head.next = list; // 新链表的指针 let p = head; while (p1 && p2) { if (p1.val <= p2.val) { // 链表加长 p.next = new ListNode(p1.val); // 指针移动 p1 = p1.next; p = p.next; } else { // 链表加长 p.next = new ListNode(p2.val); // 指针移动 p2 = p2.next; p = p.next; } } // 这里链表1、2肯定有一个遍历完了，剩下的接上去就行 p.next = p1 ? p1 : p2; // 头结点的引用就是在这时候用到的，当然首个空节点不要 return head.next; }
可以看下官方视频
练习：删除重复节点
网络异常，图片无法展示
|
- 因为有序，所以重复的节点肯定是相邻的
- 考虑边界问题，额外增加一个头结点
- 从头遍历，指针指向当前节点，判断和下一个节点是相同的话，删除下一个节点
- 不相同的话，指针向前挪动
function ListNode(val, next) { this.val = val; this.next = null; } var deleteDuplicates = function (head) { let head = new ListNode(); head.next = list; let p = head; while (p && p.next) { // 相邻节点是不是相等，这里注意相等的话，一直删除节点，直到不相等的时候，指针才挪动 while (p && p.next && p.val === p.next.val) { // 删除的时候，有下下节点，直接修改指向;没有下下节点的话，就是尾结点，直接置为空 p.next = p.next.next ? p.next.next : null; } // 指针挪动 p = p.next; } return head.next; };
虽然看着两层循环，但其实，每个节点只遍历一次，所以时间复杂度是 O(n)，空间复杂度是 O(1).
练习：删除重复节点升级
网络异常，图片无法展示
|
这里，重复的节点本身也会删除。
本身也被删除，非常重要！
因为链表的删除，必须要知道前置节点！ 所以，我们遍历的时候，指针指向当前节点，但比较的是下一个节点和下下一个节点
- 边界的问题，加上空的前置节点
- 当值相同的时候，将这两个节点删除，然后看下一个节点是不是和刚刚的值相等，相等的话继续删除，一直到不相等，这样就会将删除的相邻节点都会删除
- 当值不同的时候，指针移动
function ListNode(val, next) { this.val = val; this.next = null; } var deleteDuplicates = function (list) { let head = new ListNode(); head.next = list; let p = head; // 因为比较指针后两个节点，所以必须判断在的情况 while (p && p.next && p.next.next) { /* 节点值相同的全部删除 开始 */ // 开始是两个节点值相同，将这两个节点都删除 if (p.next.val === p.next.next.val) { let cur = p.next.val; p.next = p.next.next.next ? p.next.next.next : null; // 然后看下一个节点是不是和删除的节点一样，一样的话，接着删除，直到下一个节点的值和删除的节点不一样 while (p.next && p.next.val === cur) { p.next = p.next.next ? p.next.next : null; } /* 节点值相同的全部删除 结束 */ } else { p = p.next; } } return head.next; };
时间复杂度依旧是O(n)，时间复杂度是O(1)
