大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
剑指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 中把头节点当做了虚拟节点,体会两种解法的细微差别
总结
事实上,使用双指针的链表题还有很多,这里就举几个常见的栗子????,并且在链表题中虚拟头节点也是个很棒的技巧,有时可以减少很多额外的判断
完结撒花????
公众号【今天也要写bug】