Algorithm-List2
date
Oct 28, 2023
slug
algorithm-list2
status
Published
tags
algorithm
type
Post
https://twitter.com/tangdahe
summary
list opt
24 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
双指针法
建议使用虚拟头结点，这样会方便很多，要不然每次针对头结点（没有前一个指针指向头结点），还要单独处理。
- 每次处理两个即，curr 、curr.Next
- prev 需要指向反转后的头部节点
- 两个节点内部需要调换顺序
- 两个节点中后者节点需要继续保持链表后续链接，不然遇到奇数节点后续就断了
递归法
相对于双指针法，逻辑清晰，代码量更少
- 需要注意最终的终止条件
- 当前阶段，需要向上层返回 next 节点作为上层的下个连结节点
- 当前阶段，当前节点需要连接递归下一层的头部节点
- 当前阶段，需要调换两个节点
19 删除链表的倒数第 N 个节点
双指针
- 假设要删除倒数第 2 个节点，我们需要保留其前置节点 3，这样方便我们将
second.next = 5
- 快慢指针之间的距离为 n，当快指针到最后的时候，慢指针恰好为目标节点的前置节点
- 有一种特例，加入需要删除的节点就是第一个节点，我们是找不到其前置节点，因此需要给原始链表添加一个虚拟头节点方便操作
递归
- 假设要删除倒数第 2 个节点，我们需要保留其前置节点 3，这样方便我们将
3.next = 5
- 所以我们从最底层开始往上递归，nil 为最底层，返回 int = 0，每往上递归一层 idx++
- 直到倒数第四层 3，底层递归回来 idx 为 2 符合传入的 n，测试直接处理
curr.next = curr.next.next即可
- 有一种特例，加入需要删除的节点就是第一个节点，我们是找不到其前置节点，因此需要给原始链表添加一个虚拟头节点方便操作
160 相交链表
- A B 两个链表分别从其头节点开始遍历，pa pb 分别指向头节点
- 当 pa 遍历完 A 链表时，pa = headB。同理 pb = headA
- 再进行遍历，直到 pa = pb 位置
- 这里不用担心不存在相交节点的情况，因为假设不相交，最后 pa = pb = nil，依旧可以返回正确结果
141 环形链表
给你一个链表的头节点
head ，判断链表中是否有环。
如何判断链表有环？
快慢指针：
可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢
首先第一点：fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。
那么来看一下，为什么fast指针和slow指针一定会相遇呢？
可以画一个环，然后让 fast指针在任意一个节点开始追赶slow指针。
会发现最终都是这种情况， 如下图：
fast和slow各自再走一步， fast和slow就相遇了
这是因为fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。
142 环形链表2
给定一个链表的头节点
head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
这道题目，不仅考察对链表的操作，而且还需要一些数学运算。
主要考察两知识点：
- 判断链表是否环：同上述题目
- 如果有环，如何找到这个环的入口
如果有环，如何找到这个环的入口
此时已经可以判断链表是否有环了，那么接下来要找这个环的入口了。
假设从头结点到环形入口节点 的节点数为 x。 环形入口节点到 fast 指针与 slow 指针相遇节点 节点数为 y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：
那么相遇时： slow 指针走过的节点数为:
x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast 指针在环内多走了 n 圈才遇到 slow 指针， （y+z）为 一圈内节点的个数 A。因为 fast 指针是一步走两个节点，slow 指针一步走一个节点， 所以 fast 指针走过的节点数 = slow 指针走过的节点数 * 2：
(x + y) * 2 = x + y + n (y + z)两边消掉一个（x+y）:
x + y = n (y + z)因为要找环形的入口，那么要求的是 x，因为 x 表示 头结点到 环形入口节点的的距离。
所以要求 x ，将 x 单独放在左面：
x = n (y + z) - y ,再从 n(y+z) 中提出一个（y+z）来，整理公式之后为如下公式：
x = (n - 1) (y + z) + z 注意这里n一定是大于等于 1 的，因为 fast 指针至少要多走一圈才能相遇 slow 指针。那么 n 如果大于 1 是什么情况呢，就是 fast 指针在环形转 n 圈之后才遇到 slow 指针。
其实这种情况和 n 为 1 的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了 (n-1) 圈，然后再遇到 index2，相遇点依然是环形的入口节点。