算法基础知识学习笔记-链表
一. 关于链表
链表由一系列节点组成,每个节点都包含了data(数据)和next(下一个节点的指针)组成,下图就是一个简单的链表示意图
关于节点的代码
class ListNode { constructor(val) { this.val = val; this.next = null; } }复制代码
组成链表
let node1 = new ListNode(1) let node2 = new ListNode(2) let node3 = new ListNode(3) node1.next = node2 node2.next = node3 console.log(node1) // head复制代码
二. 做题笔记
1. 翻转链表 (力扣206题)
迭代翻转 (思路:遍历每个节点,把当前节点的指针指向前一个)
function reverse (head) { if (!head || !head.next) return head let curr = head, // 当前要遍历的节点 pre = null // 当前节点的前一个节点 while (curr) { let next = curr.next // 暂存当前节点的下一个节点 curr.next = pre // 当前节点的指针指向前一个 pre = curr // 前一个节点后移一位 curr = next // 当前节点后移一位 } // 循环终止,curr为null,curr的前一位即pre是新的head return pre };复制代码
递归翻转(思路:从后往前操作)
function reverse (head) { if (!head || !head.next) return head let tail = head.next // 下一个节点 let newHead = reverse(tail) head.next = tail.next // 这句特别不好理解 tail.next = head // 下一个节点的指针指向自己 return newHead }复制代码
// 比较好理解的迭代代码 function reverse (head) { function reverseFn (head, pre){ if(!head) return pre let tail = head.next // 缓存下一个节点 head.next = pre // 翻转 return reverse(tail, head) } return reverseFn(head, null) }复制代码
1-1. 翻转链表延伸
翻转从头到固定位数的节点
function reverseN (head, n) { // 多一个参数 if (!head || !head.next) return head if (n === 1) return head // 与递归翻转不一样的地方 let tail = head.next let newHead = reverse(tail, n - 1) // 多一个参数 head.next = tail.next tail.next = head return newHead }复制代码
翻转从固定位置到固定位置的节点 (力扣92题)
function reverseBetween (head, left, right) { let headpre = new ListNode(0, head), // 创建虚拟头节点 p = headpre const cnt = right - left + 1 // 要翻转的位数 while (--left) { // 找到要翻转的起始节点的前一位 (假设left为1,循环不进入,p为虚拟头节点) p = p.next } p.next = reverseN(p.next, cnt) // 上边的reverseN方法 return headpre.next };复制代码
k个一组,翻转链表 (力扣25题)
function reverseKGroup (head, k) { function reverseN () {} // 同上 function hasN (head, n) { // 判断是否够n个一组 let p = head let cnt = n while (p && --n ) { // 查询长度 p = p.next } if (!p) return head // 不够翻转,原封不动返回 return reverseN(head, cnt) } let newHead = new ListNode(0, head), p = newHead, q = p.next // 如果发生翻转,q即为下一组翻转的头节点的前一个节点 while (1) { p.next = hasN(q, k) // 虚拟头节点指向新的头节点 if (p.next == q) { // 如果不够翻转的时候,结束循环 break } p = q q = p.next } // 简写 /* while ((p.next = hasN(q, k)) != q) { p = q q = p.next } */ return newHead.next }复制代码
2. 删除链表的倒数第 N 个节点(力扣19题)
思路:创建一个虚拟头节点,创建两个指针,第一个指针指向虚拟头节点,第二个指针指向头节点,第二个指针先走N步,然后两个指针一起开始走,当第二个指针走到null的时候,第一个指针即指向了要被删除的节点的前一个节点
function removeNthFromEnd (head, n) { if (!head) return null let newHead = new ListNode(0, head) let p = newHead, q = head while (n--) q = q.next while (q) { q = q.next p = p.next } p.next = p.next.next return newHead.next }复制代码
3. 删除排序链表中重复节点(力扣83题)
``` function deleteDuplicates (head) { let p = head while (p && p.next) { let next = p.next while (p.val === (next && next.val)) { // 循环找到所有重复节点 p.next = p.next.next next = p.next } p = p.next } return head } ```复制代码
4. 力扣82题
``` function deleteDuplicates (head) { let newHead = new ListNode(NaN, head) // 头节点如果会发生变化,创建虚拟头节点方便操作 let pre = newHead let p = head while (p && p.next) { if (p.val === p.next.val) { // 如果发现重复节点 let next = p.next while ((next && next.val) === p.val) { // 遍历找到下一个不重复的节点 next = next.next } pre.next = next // 把重复节点全部跳过 } else { pre = pre.next // 如果没有重复,则上一个节点右移一位 } p = pre.next // 当前遍历的节点直接跳到下一个未重复的节点 } return newHead.next } ```复制代码
5. 环形链表(力扣141题)
思路:设定快慢指针,如果存在链表有环,则快指针必定会追上慢指针
function hasCycle (head) { if (!head || !head.next) return false let slow = fast = head do { slow = slow.next // 慢指针一次右移一位 fast = fast.next.next // 快指针一次右移两位 } while (slow !== fast && fast && fast.next) return fast != null && fast.next != null }复制代码
5-1. 延伸(力扣142题)
思路:第一次相遇时的位置距离环的起点等于从头开始到环的起点位置
function detectCycle (head) { if (!head || !head.next) return null let slow = fast = head do { slow = slow.next fast = fast.next.next } while (slow !== fast && fast && fast.next) // 到这里为止同上边一样 if (fast && fast.next) { // 如果有环 slow = head // 设置其中一个节点从头开始,并以相同的速度 while (fast != slow) { // 当再次相等时 fast = fast.next slow = slow.next } return fast } return null }复制代码
6. 旋转链表 (力扣61题)
思路:首先让链表首尾相接形成环形链表,然后继续右移length - k%length
function rotateRight (head, k) { if (!head || !head.next) return head let last = head let length = 1 while (last.next) { length++ last = last.next } last.next = head // 首尾相接 let num = length - k%length // 长度 - k while (num--) { last = last.next } let newHead = last.next // 暂存头节点 last.next = null // 断开 return newHead }复制代码
三. 链表扩展
1. js实现链表
``` class LinkList { constructor() { this._length = 0 this._head = null this._tail = null } append () {} // 添加一个节点 get () {} // 返回指定索引位置的节点 head () {} // 返回头节点 tail () {} // 返回尾节点 length () {} // 返回链表长度 isEmpty () {} // 返回链表是否为空 clear () {} // 清空链表 indexOf () {} // 返回指定节点的索引 remove () {} // 删除指定位置的节点 insert () {} // 在指定位置插入一个节点 } ```
作者:姚头
链接:https://juejin.cn/post/7025191838483120159