关于javascript:前端也该刷点算法题双指针解链表题也太香了叭

6次阅读

共计 5079 个字符，预计需要花费 13 分钟才能阅读完成。

剑指 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. 相交链表

思路

双指针 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;
}

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

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

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】

正文完

javascript

发表至： javascript

2022-08-31

0

了解语音交互：从“若琪，今天杭州的天气”发生了什么？

关于javascript:Nodejs-fspath模块

关于javascript:JS-如何替换字符串内容

关于javascript:uniapp-打包IOS-更新AppStore版本

关于phoenix:Phoenix单机版安装遇到的启动问题

关于javascript:前端也该刷点算法题双指针解链表题也太香了叭

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

同步双指针

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

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

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

快慢双指针

1 查找链表的两头节点

2 判断链表中是否有环

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

站内搜索