链表
移除链表元素
想要移除一个链表的节点,其实特别简单,只需要 p.next = p.next.next 即可。也就是说,要想删除某个节点,只要找到删除节点的前一个节点 p,然后让 p 的下一个节点指向删除节点的下一个节点即可。但是问题在于,如果移动的是头节点呢?头节点找不到前一个节点,所以我们其实只需要把头节点指向下一个节点就行了。但是这样删除方法其实并没有统一,这就是 dummyHead 虚拟头节点引入的意义 —— 统一头节点和非头节点的处理方法。
另外,这里 while 循环的条件为什么是 p.next,而不是 p 呢?因为假设我们要删除某个节点,就需要找到它的前一个节点,但是对于单向链表来说,前一个节点是获取不到的,所以我们只能换一种思考方式:从前一个节点 p 开始遍历,然后需要删除的时候删除掉 p.next 这个节点。
function removeElements(head: ListNode | null, val: number): ListNode | null { const dummyHead = new ListNode(-1, head) // 这里 p 指向的是被删元素的上一个元素 let p = dummyHead while (p.next) { if (p.next.val === val) { p.next = p.next.next } else { p = p.next } } return dummyHead.next }
设计链表
这是一道非常非常复杂的模拟题,甚至比 LRU 还要复杂得多,复杂主要体现在太容易出错了,我也因为一些细节问题 debug 了挺长时间。题目要求我们可以在单链表和双链表之间做选择,很显然这里选择双链表会更合适,可以保证时间复杂度更小。因为对于尾部的插入我们可以直接利用虚拟尾节点实现 O(1) 插入;对于中间部分的节点插入,我们也可以计算出该节点的遍历方向,靠左就从左向右遍历,靠右就从右向左遍历,保证了最小遍历次数。但是对于节点的插入,依然是很容易出错的,这里建议是使用画图的方法,确保不要写漏其中的某个关系。以 addAtIndex 函数为例:
class LinkedNode { public prev: null | LinkedNode = null public next: null | LinkedNode = null public val: number constructor(val: number) { this.val = val } } class MyLinkedList { private dummyHead = new LinkedNode(-1) private dummyTail = new LinkedNode(-1) private length = 0 constructor() { this.dummyHead.next = this.dummyTail this.dummyTail.prev = this.dummyHead } get(index: number) { if (index >= this.length || index < 0) { return -1 } return this.getNode(index).val } addAtHead(val: number) { const newHead = new LinkedNode(val) newHead.next = this.dummyHead.next newHead.prev = this.dummyHead newHead.next.prev = newHead this.dummyHead.next = newHead this.length++ } addAtTail(val: number) { const newTail = new LinkedNode(val) newTail.prev = this.dummyTail.prev newTail.next = this.dummyTail newTail.prev.next = newTail this.dummyTail.prev = newTail this.length++ } addAtIndex(index: number, val: number) { if (index > this.length) { return } if (index < 0) { this.addAtHead(val) return } if (index === this.length) { this.addAtTail(val) return } const p = this.getNode(index) const newNode = new LinkedNode(val) newNode.next = p newNode.prev = p.prev p.prev.next = newNode p.prev = newNode this.length++ } deleteAtIndex(index: number) { if (index >= 0 && index < this.length) { const p = this.getNode(index) p.prev.next = p.next p.next.prev = p.prev this.length-- } } /** 注意该函数不包括边界判断 */ private getNode(index: number) { const findFromLeft = index < Math.floor(this.length / 2) if (!findFromLeft) { index = this.length - 1 - index } let p = findFromLeft ? this.dummyHead.next : this.dummyTail.prev for (let i = 0; i < index; i++) { p = findFromLeft ? p.next : p.prev } return p } }
反转链表
反转链表有双指针和递归两种写法,都需要掌握。双指针的解法比较容易理解,但是递归的方法会让人比较懵。我们可以选择从双指针解法推导出递归的解法。具体怎么推导有点玄学,文字很难说明清楚,可以看代码随想录的视频讲解。
// 双指针 function reverseList(head: ListNode | null): ListNode | null { let prev = null, cur = head // 边界条件,当 cur 为 null 时,pre(cur 的前一个节点)刚好指向链表尾部,也就是反转之后的头节点 while (cur) { // 存储 cur 的下一个节点,否则链表无法继续遍历下去 const temp = cur.next cur.next = prev prev = cur cur = temp } return prev }
// 递归 function reverseList(head: ListNode | null): ListNode | null { return helper(null, head) function helper(prev: ListNode | null, cur: ListNode | null) { if (!cur) { return prev } const temp = cur.next cur.next = prev return helper(cur, temp) } }
两两交换链表中的节点
这道题目也算是有一定难度的题目,对于边界的处理和链表基本操作的要求都比较高。
先思考一下边界条件,这道题要两两交换链表的节点,比如说要交换 2 和 3 节点,就需要在 2 前面的节点 1(假设叫 p)执行类似 p.next.next = 节点 2 的操作,那么对于头节点我们就要额外判断处理。所以这里为了统一操作,我们可以选择使用 dummyHead,如下所示。
然后思考边界条件,分为奇偶处理。如果现在有奇数个节点,比如图中有 5 个节点,我们的 current 指针会依次指向 dummyHead,进行节点 1 和节点 2 的交换;然后指向节点 2,进行节点 3 和 节点 4 的交换;然后指向节点 4,此时节点 5 已经是尽头,不需要再进行交换。所以当有奇数个节点时边界为 current.next.next !== null。然后我们再设想一下,对于偶数个节点,例如现在如果没有节点 5,那么 4 相当于直接指向了 null,此时的边界条件很显然是 current.next !== null。综上可得边界条件是 current.next !== null && current.next.next !== null。
现在开始进行交换。让 dummyHead 的指针指向 2,然后 2 的指针再指向 1,然后 1 的指针再指向 3。
这里就涉及到如果获取节点 1 了,我们执行完 current.next = current.next.next 之后,其实 current.next 就已经不再是节点 1 了,所以我们需要先用一个临时变量存储一下节点 1。同样的道理,我们节点 2 指向节点 1 之后,就拿不到节点 3 了,那 1 就没办法指向节点 3 了,所以我们还需要一个临时变量来存储一下节点 3 的值。明白这些之后我们就可以实现这道题的代码了。实现起来还是比较复杂的,但是只要结合画图解决问题,就会难度小很多。
function swapPairs(head: ListNode | null): ListNode | null { const dummyHead = new ListNode(-1, head) let p = dummyHead while (p.next && p.next.next) { const temp = p.next // 节点 1 const temp1 = p.next.next.next // 节点 3 p.next = p.next.next // dummy 指向节点 2 p.next.next = temp // 节点 2 指向节点 1 temp.next = temp1 // 节点 1 指向节点 3 p = p.next.next // 移动 dummy(此时节点 1 和节点 2 位置已经变换,但是并不影响我们继续遍历) } return dummyHead.next }
删除链表的倒数第 N 个结点
这道题其实是一个经典的快慢指针问题。首先思考一下,要删除一个节点该怎么做,很显然,我们需要获得这个节点的前一个节点。现在假设 n = 3。令快指针 fast 和慢指针 slow 都指向 dummyHead,然后我们让指针 fast 先走 n 步,fast 就会来到指针 3 的位置。然后我们再同时移动 fast 和 slow 直到 fast 移动到 null。显然此时 fast 指向 null,而 slow 指向 2。我们要删除倒数第 3 个节点 2,就要让 slow 指向 1,而 现在 slow 指向了 2,多指了一位,所以 fast 要移动多一步,也就是我们开始的时候需要先让 fast 移动 n + 1 步。
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null { const dummyHead = new ListNode(-1, head) let fast = dummyHead, slow = dummyHead for (let i = 0; i < n + 1; i++) { fast = fast.next } while (fast) { fast = fast.next slow = slow.next } slow.next = slow.next.next return dummyHead.next }
链表相交
我们先明确一下自己需要解决的问题。假设目前 curA 指向链表 A 的头结点,curB 指向链表 B 的头结点,如果 curA 和 curB 分别直接在两条链表上移动,并不能同时走到公共节点,也就无法得到相交节点了。所以我们要解决的问题就是通过某些方式,使得 curA 和 curB 能够同时到达相交节点。而且我们很容易知道,如果节点 A 和节点 B 相交于点 P,则 P 后面的部分都是两链表的重叠部分。因此,只要让两个链表的尾部对齐,就可以进行对比了。
我们先求出两个链表的长度,并求出两个链表长度的差值,然后让 curA 移动,直到两个链表尾部对齐,而且可以同步移动节点,如图:
此时我们就可以比较 curA 和 curB 是否相同,如果不相同,同时向后移动 curA 和 curB,如果遇到 curA === curB,则找到交点。
function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null { let curA = headA, curB = headB let lenA = 0, lenB = 0 while (curA) { lenA++ curA = curA.next } while (curB) { lenB++ curB = curB.next } curA = headA curB = headB if (lenA < lenB) { [lenA, lenB, curA, curB] = [lenB, lenA, curB, curA] } let gap = lenA - lenB // 补齐两个链表长度之差 while (gap--) { curA = curA.next } while (curA) { if (curA === curB) { return curA } curA = curA.next curB = curB.next } return null }
环形链表II
这道题定义快慢指针,快指针一次走 2 个节点,慢指针一次走一个节点。那么为什么要这么定义呢?假设现在快慢指针都已经进入到了环内,那么快指针相对于慢指针的移动速度是一次一个节点,所以快指针是一个节点一个节点地靠近慢指针,也就是必定会在环内相遇;反之如果快慢指针最终没有相遇,则说明链表无环。此时已经可以判断链表是否有环了,那么接下来要找这个环的入口了。
相遇时:slow 指针走过的节点数为: x + y, fast 指针走过的节点数:x + y + n (y + z),n 为 fast 指针在环内走了 n 圈才遇到 slow 指针,(y+z) 为一圈内节点的个数。
因为 fast 指针一步走两个节点,slow 指针一步走一个节点, 所以 fast 指针走过的节点数 = slow 指针走过的节点数 * 2,也就是
(x + y) * 2 = x + y + n (y + z)
两边消掉一个(x+y)后得到:
x + y = n (y + z)
因为要找环形的入口,也就是说要求的是 x。将 x 单独放在左边:
x = n (y + z) - y
再从 n (y+z) 中提出一个 (y+z) 来,整理公式之后为如下公式:
x = (n - 1) (y + z) + z
注意这里 n 一定是大于等于 1 的,因为 fast 指针至少要多走一圈才能相遇 slow 指针。当 n 为 1 的时候,公式就化为:
x = z
这就意味着,从头结点 index1 出发一个指针,从相遇节点 index2 也出发一个指针,这两个指针每次只走一个节点,那么当这两个指针相遇的时候就是环形入口的节点。那么 n 如果大于 1 是什么情况呢,就是 fast 指针在环形转 n 圈之后才遇到 slow 指针。其实这种情况和 n 为 1 的时候效果是一样的,一样可以通过这个方法找到环形的入口节点,只不过,index2 指针在环里多转了 (n - 1) 圈,然后再遇到 index1,相遇点其实依然是环形的入口节点。
知道原理之后,其实这道题的代码实现倒是几乎没什么难度。
function detectCycle(head: ListNode | null): ListNode | null { let fast = head, slow = head while (fast && fast.next) { fast = fast.next.next slow = slow.next if (slow === fast) { let index1 = head, index2 = slow while (index1 !== index2) { index1 = index1.next index2 = index2.next } return index1 } } return null }