前端也该刷点算法题——双指针解“链表”题也太香了叭！

2年前 (2022) 程序员胖胖胖虎阿

372 0 0

双指针解“链表”题也太香了叭！

同步双指针

1 查找链表中倒数第 k 个节点

剑指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 中添加了一个虚拟头节点，虚拟头节点在解决链表相关的一些题目时非常有用，体会一下不用虚拟头节点和使用虚拟头节点的差别

2 删除链表中倒数第 k 个节点

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;
}

注：尝试不用虚拟头节点解此题，体会虚拟头节点的妙处

3 查找两条链表的相交节点

160. 相交链表

前端也该刷点算法题——双指针解“链表”题也太香了叭！

思路

双指针 p1 和 p2 分别从 headA 和 headB 出发
如果 p1 走完了链表 A，就从 headB 接着走；同理，如果 p2 走完了链表 B，就从 headA 接着走
在这种走法下，p1 和 p2 一定同时走完
如果两条链表相交，那么 p1 和 p2 一定会在交点相遇，因为从交点开始到结束点，两条链表的路径是相同的，于是 p1 和 p2 从结束点向前推能同时到达交点
如果两条链表不相交，则 p1 和 p2 全程不会相遇

代码

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;
}

快慢双指针

1 查找链表的中间节点

876. 链表的中间结点

前端也该刷点算法题——双指针解“链表”题也太香了叭！

思路

这题我们让两个指针同时走，不过两个指针的速度不同，分为快慢指针
我们让慢指针每次走 1 步，快指针每次走 2 步
当快指针走完链表，即指向 null，慢指针就走到了中间节点的位置

前端也该刷点算法题——双指针解“链表”题也太香了叭！

代码

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;
}

2 判断链表中是否有环

141. 环形链表

前端也该刷点算法题——双指针解“链表”题也太香了叭！

思路

设定快慢两指针 fastP 、slowP
fastP 每次走 2 步，slowP 每次走 1 步
如果链表中没有环，那么 fastP 最终会先走到 null
如果链表中有环，那么 fastP 会先进入环，并在环中转圈
当 slowP 进入环后，fastP 开始追赶 slowP，最终一定能追上
当 fastP 追上 slowP 时，若 slowP 走了 n 步，不难得出，fastP 走了 2n 步或 2n - 1 步

代码

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;
}

3 查找链表中环的入口节点

142. 环形链表 II

前端也该刷点算法题——双指针解“链表”题也太香了叭！

思路

此题和上一题的思路大致相同，不过在上一题的基础上更进一步
上一题中提到，如果快指针追上慢指针，且假设 slowP 走了 n 步，不难得出，fastP 走了 2n 步或 2n - 1 步。出现走 2n - 1 步的原因是可能存在 fastP 最后只走 1 步就追上 slowP 的情况
不过即使规定 fastP 一定要走偶数步，fastP 和 slowP 也一定能在某点相遇，因为在 fastP 走 2 步，slowP 走 1 步的前提下，两者的间距会 -1，所以最终两者会相遇
现在设 slowP 走了 n 步，fastP 走了 2n 步，两者相遇
则 fastP 比 slowP 多走了 n 步，这 n 步是环周长的整数倍
假设 slowP 从环起点开始走了 k 步后，两者相遇，则从链表头节点开始走 n - k 步（头节点算第 1 步）就能到达环起点
而从环起点走 k 步到达相遇点，再走 n - k 步就能到达相遇点，因为从环起点走 k + n - k = n 步回到环起点（见第5点，因为 n 是环周长的整数倍）
所以我们可以先用快慢指针找到两者的相遇点，然后让快指针从头开始，慢指针从相遇点开始，并且两者变成同步指针，则两者再次相遇即为环的起点

代码

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】

版权声明：程序员胖胖胖虎阿发表于 2022年9月16日上午8:00。
转载请注明：前端也该刷点算法题——双指针解“链表”题也太香了叭！ | 胖虎的工具箱-编程导航

相关文章

IDEA专业版激活码(Intellij IDEA全新破解教程,激活至2099年)

程序员胖胖胖虎阿

370

IntelliJ IDEA最新免费激活码(idea的2022.2破解版每日更新)

程序员胖胖胖虎阿

135

【多线程】线程池的七种创建方式，线程池的拒绝策略，线程池看这篇就够了

程序员胖胖胖虎阿

252

Java面试题超详细讲解系列之十一【MongoDB篇】

程序员胖胖胖虎阿

200

idea的永久破解版(IntelliJ IDEA最新版破解教程,最新有效IDEA激活码)

程序员胖胖胖虎阿

174

收藏了！7 个开源的 Spring Boot 前后端分离优质项目

程序员胖胖胖虎阿

325

暂无评论

暂无评论...

致力于称为最好的程序员导航网站

友链申请免责声明关于我们

Copyright © 2022 胖虎的工具箱-编程导航 陇ICP备2022001249号