首页 > 编程语言 >前端也该刷点算法题——双指针解“链表”题也太香了叭！

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

时间：2022-08-31 20:24:13浏览次数：83  
标签：slowP head p1 太香 fastP next 链表 刷点

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

同步双指针

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

剑指Offer22.链表中倒数第k个节点

截屏2022-08-31 14.50.04

思路：

  1. 假设链表的长度为n，不难得出倒数第k个节点即为整数第n + 1 - k。

  2. 如果一个指针从头节点开始走k步（头节点算作第1步），则还需n + 1 - k步才能走完链表（到达尾节点的next，即 null）。

  3. 我们用双指针，一个指针先走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个结点

截屏2022-08-31 15.22.40

思路

  1. 删除和查找倒数第 k 个节点的思路大致相同

  2. 唯一的区别是删除倒数第 k 个节点时我们应该查找倒数第 k + 1 个节点，然后让其 next 指向 next 的 next。

    因为我们要查找倒数第 k + 1 个节点，所以应该让第一个指针先走 k + 1 步

  3. 此外删除的有可能是第 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. 相交链表

截屏2022-08-31 16.18.28

思路

  1. 双指针 p1 和 p2 分别从 headA 和 headB 出发
  2. 如果 p1 走完了链表 A，就从 headB 接着走；同理，如果 p2 走完了链表 B，就从 headA 接着走
  3. 在这种走法下，p1 和 p2 一定同时走完
  4. 如果两条链表相交，那么 p1 和 p2 一定会在交点相遇，因为从交点开始到结束点，两条链表的路径是相同的，于是 p1 和 p2 从结束点向前推能同时到达交点
  5. 如果两条链表不相交，则 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. 链表的中间结点

截屏2022-08-31 15.42.12

思路

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

未命名文件 (2)

代码

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. 环形链表

截屏2022-08-31 17.16.50

思路

  1. 设定快慢两指针 fastP 、slowP
  2. fastP 每次走 2 步，slowP 每次走 1 步
  3. 如果链表中没有环，那么 fastP 最终会先走到 null
  4. 如果链表中有环，那么 fastP 会先进入环，并在环中转圈
  5. 当 slowP 进入环后，fastP 开始追赶 slowP，最终一定能追上
  6. 当 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

截屏2022-08-31 19.04.28

思路

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

代码

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 中把头节点当做了虚拟节点，体会两种解法的细微差别

总结

事实上，使用双指针的链表题还有很多，这里就举几个常见的栗子

标签：slowP,head,p1,太香,fastP,next,链表,刷点
From： https://www.cnblogs.com/bidong/p/16644409.html

相关文章

  • leetcode 1019. 链表中的下一个更大节点 js实现
    给定一个长度为 n 的链表 head对于列表中的每个节点，查找下一个更大节点的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值严格大于它的值。返回......
  • NowCoder BM1 反转链表
    描述给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。NowCoderBM1反转链表importjava.util.*;/*public......
  • Javascript中的链表
    Javascript中的链表数据结构的介绍文章。链表概念与应用于Javascript语言的实际示例。介绍数据结构是一种有效处理大量数据的手段，了解它的结构和组成为我们提供了更......
  • 数据结构之链表的原理
    链表：在计算机中用一组任意的存储单元存储线性表的数据元素称为链式存储结构，这组存储结构可以是连续的，也可以是不连续的，因此在存储数据元素时可以动态分配内存。注：在java中......
  • 从零构建链表
    最重要的头节点是这样创建的：        Node*Head=newNode;//头节点不存储数据        Head->next=NULL;        Node*pre=Head......
  • 83. 删除排序链表中的重复元素
    83.删除排序链表中的重复元素#由于是已排序的链表，判断前后是否为相同元素如果是则连接下下个不是则向前移动#code：#Definitionforsingly-linkedlist.#classLis......
  • 链表节点删除
      代码：1importjava.util.*;23publicclassMain{4publicstaticvoidmain(String[]args){5Scannerscan=newScanner(System.in);......
  • LeetCode 21. 合并两个有序链表
    题目题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的......
  • 61. 旋转链表
    提示：这个题目比较简单，只需要找到待断处的前一个节点就行，题目描述：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。案例：输入：head=[1,2,3,4,......
  • 21级数据结构与算法实验2——链表
    21级数据结构与算法实验2——链表28天7-1单链表的创建及遍历分数30作者陈晓梅单位广东外语外贸大学读入n值及n个整数，建立单链表并遍历输出。输入格式:读入n及......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99