剑指Offer22.链表中倒数第k个节点
思路:
假设链表的长度为n
,不难得出倒数第k
个节点即为整数第n + 1 - k
。
如果一个指针从头节点开始走k
步(头节点算作第1步),则还需n + 1 - k
步才能走完链表(到达尾节点的next,即 null)。
我们用双指针,一个指针先走k
步,然后两个指针同时走n + 1 - k
步,其中一个指针走完链表,另一个指针走到第n + 1 - k
个节点处,即倒数第k
个节点
代码
JS
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var getKthFromEnd = function (head, k) { let p1 = head; // 注意此处 i < k - 1,因为 p1 赋值时算作第 1 步 for (let i = 0; i < k - 1; i++) { p1 = p1.next; } let p2 = head; p1 = p1.next; // 同理 p2 赋值算作第 1 步,所以 p1 也要走 1 步 while (p1) { p1 = p1.next; p2 = p2.next; } return p2; }; // 时间复杂度 O(n) n为链表长度 // 空间复杂度 O(1)
TS
/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */ function getKthFromEnd(head: ListNode | null, k: number): ListNode | null { const dummyHead = new ListNode(); dummyHead.next = head; let p1 = dummyHead; for (let i = 0; i < k; i++) { p1 = p1.next; } let p2 = dummyHead; while (p1) { p1 = p1.next; p2 = p2.next; } return p2; } // 时间复杂度 O(n) n为链表长度 // 空间复杂度 O(1)
注:JS 和 TS 的实现略微有些不同,TS 中添加了一个虚拟头节点,虚拟头节点在解决链表相关的一些题目时非常有用,体会一下不用虚拟头节点和使用虚拟头节点的差别
19.删除链表的倒数第N个结点
思路
删除和查找倒数第 k 个节点的思路大致相同
唯一的区别是删除倒数第 k 个节点时我们应该查找倒数第 k + 1 个节点,然后让其 next 指向 next 的 next。
因为我们要查找倒数第 k + 1 个节点,所以应该让第一个指针先走 k + 1 步
此外删除的有可能是第 1 个节点,见示例2,此时删除的是倒数第 1 个节点,所以我们要查找倒数第 2 个节点,然而链表总共才 1 个节点,因此我们引入虚拟头节点来解决
代码
JS
var removeNthFromEnd = function (head, n) { const dummyHead = new ListNode(); dummyHead.next = head; // 将虚拟头节点接入链表 let p1 = dummyHead; // p1 先走 n + 1 步 for (let i = 0; i < n + 1; i++) { p1 = p1.next; } let p2 = dummyHead; while (p1) { p1 = p1.next; p2 = p2.next; } p2.next = p2.next.next; // 注意不是返回 head,因为 head 有可能被删除 return dummyHead.next; }; // 时间复杂度 O(n) n为链表长度 // 空间复杂度 O(1)
TS
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null { const dummyHead = new ListNode(); dummyHead.next = head; let p1 = dummyHead; for (let i = 0; i < n + 1; i++) { p1 = p1.next; } let p2 = dummyHead; while (p1) { p1 = p1.next; p2 = p2.next; } p2.next = p2.next.next; return dummyHead.next; }
注:尝试不用虚拟头节点解此题,体会虚拟头节点的妙处
160. 相交链表
思路
代码
JS
var getIntersectionNode = function (headA, headB) { let p1 = headA; let p2 = headB; while (p1 || p2) { if (p1 === p2) return p1; p1 = p1 ? p1.next : headB; p2 = p2 ? p2.next : headA; } return null; }; // 时间复杂度 O(n + m) m、n 分别为两条链表长度 // 空间复杂度 O(1)
TS
function getIntersectionNode( headA: ListNode | null, headB: ListNode | null ): ListNode | null { let p1 = headA; let p2 = headB; while (p1 || p2) { if (p1 === p2) return p1; p1 = p1 ? p1.next : headB; p2 = p2 ? p2.next : headA; } return null; }
876. 链表的中间结点
思路
代码
JS
var middleNode = function (head) { const dummyHead = new ListNode(); dummyHead.next = head; let fastP = dummyHead; let slowP = dummyHead; while (fastP) { slowP = slowP.next; fastP = fastP.next; fastP && (fastP = fastP.next); } return slowP; }; // 时间复杂度 O(n) n 为链表长度 // 空间复杂度 O(1)
TS
function middleNode(head: ListNode | null): ListNode | null { const dummyHead = new ListNode(); dummyHead.next = head; let fastP = dummyHead; let slowP = dummyHead; while (fastP) { slowP = slowP.next; fastP = fastP.next; fastP && (fastP = fastP.next); } return slowP; }
141. 环形链表
思路
代码
JS
var hasCycle = function (head) { // 如果链表为空或只有 1 个节点,一定无环 if (!head || !head.next) return false; let slowP = head; let fastP = head.next; // slowP 赋值为 head 相当于走了 1 步,故 fastP 要走 2 步 while (fastP) { slowP = slowP.next; fastP = fastP.next; if (slowP === fastP) return true; fastP && (fastP = fastP.next); } return false; }; // 时间复杂度 O(n) n 为链表长度 // 空间复杂度 O(1)
TS
function hasCycle(head: ListNode | null): boolean { if (!head || !head.next) return false; let slowP = head; let fastP = head.next; while (fastP) { slowP = slowP.next; fastP = fastP.next; if (slowP === fastP) return true; fastP && (fastP = fastP.next); } return false; }
142. 环形链表 II
思路
代码
JS
var detectCycle = function (head) { if (!head || !head.next) return null; let fastP = head.next; let slowP = head; while (fastP) { if (fastP === slowP) break; slowP = slowP.next; fastP = fastP.next; fastP && (fastP = fastP.next); } if (!fastP) return null; fastP = head; slowP = slowP.next; // 注意 fastP 赋值为头节点相当于已经走了 1 步,所以 slowP 也要走 1 步 while (fastP !== slowP) { fastP = fastP.next; slowP = slowP.next; } return fastP; }; // 时间复杂度 O(n) // 空间复杂度 O(1)
TS
function detectCycle(head: ListNode | null): ListNode | null { // 这里我们把头节点当作虚拟节点 let fastP = head; let slowP = head; while (fastP) { slowP = slowP.next; fastP = fastP.next; fastP && (fastP = fastP.next); if (fastP === slowP) break; } if (!fastP) return null; fastP = head; slowP = slowP; while (fastP !== slowP) { fastP = fastP.next; slowP = slowP.next; } return fastP; }
注:我们在 TS 中把头节点当做了虚拟节点,体会两种解法的细微差别
总结
事实上,使用双指针的链表题还有很多,这里就举几个常见的栗子