代码随想录算法训练营第四天 |链表总结

今天药忘吃喽~ 2024-04-23 03:53 87阅读 0赞

##### 1、每次先加判断： #####

if (head == null) {
            return head;
        }

##### 2、ListNode dummy = new ListNode(-1, head);和ListNode dummy = new ListNode(-1);区别： #####

在Java中，ListNode dummy = new ListNode(-1, head); 和 ListNode dummy = new ListNode(-1); 的主要区别在于是否将虚拟节点的next指针指向head。

当你使用ListNode dummy = new ListNode(-1, head);时，你创建了一个哑节点（dummy node），并让它的指针指向链表的头节点。这样做的好处是，可以将头节点当做普通节点处理，不需要单独考虑。例如，**当需要对链表进行某种操作时，可以省略头节点为空的情况判断**。因为dummy节点的存在，头节点和其他节点可以进行同样的操作。

而当你使用ListNode dummy = new ListNode(-1);时，你只创建了一个值为-1的节点，但没有将其next指针指向任何其他节点。这意味着，如果你需要使用这个节点来表示链表的头部，并且需要对该链表进行操作，你需要额外进行一些处理，例如设置dummy.next = head。

所以推荐用：**ListNode dummy = new ListNode(-1, head)**

##### 3、head = new ListNode(0)和head = new ListNode()区别： #####

在Java中，ListNode通常是一个用于表示链表节点的类，具有一个整数值（或其他数据类型）和指向下一个节点的引用。对于以下两种初始化链表头节点的方式：

head = new ListNode(0)

这行代码创建了一个新的ListNode对象，并将其初始值（val）设置为0，同时下一个节点（next）默认被初始化为null。当你需要立即创建一个带有特定值（这里是0）的链表节点时，这种方式非常有用。在处理链表问题时，常常用0或特殊的占位值作为哨兵节点，来简化边界条件的处理。

head = new ListNode()

如果ListNode类没有无参数构造器或者没有显示定义构造器，这将会导致编译错误，因为没有匹配的构造函数可以调用。但如果ListNode类有一个默认的无参构造器，那么这行代码将创建一个新的ListNode对象，其值（val）默认初始化为其类型的默认值（对于int是0，对于引用类型是null），并且next属性同样会被初始化为null。然而，在实际处理链表时，这种形式不常见，除非你确实想创建一个空值节点，并且该节点的值不需要有特殊含义。

总结来说，在处理链表时，**head = new ListNode(0)更常见**，因为它明确地设置了节点的值，而head = new ListNode()仅在你需要无初始值的新节点时使用，并且类提供了无参构造函数支持这种情况。

4、环形链表精髓：

主要考察两知识点：

*  判断链表是否环
 *  如果有环，如何找到这个环的入口

#### [\#][Link 1]判断链表是否有环 ####

可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。

为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢

首先第一点：**fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。**

那么来看一下，**为什么fast指针和slow指针一定会相遇呢？**

可以画一个环，然后让 fast指针在任意一个节点开始追赶slow指针。

会发现最终都是这种情况， 如下图：

![2c0f70163dcef3f6a30a11eb1acc348e.png][]

fast和slow各自再走一步， fast和slow就相遇了

这是因为fast是走两步，slow是走一步，**其实相对于slow来说，fast是一个节点一个节点的靠近slow的**，所以fast一定可以和slow重合。

动画如下：

![ca63bdd842455d9a60adbb531c168f3b.gif][]

#### [\#][Link 2]如果有环，如何找到这个环的入口 ####

**此时已经可以判断链表是否有环了，那么接下来要找这个环的入口了。**

假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：

![7ef1cc8306dbb7e5bcffe498028b4d79.png][]

那么相遇时： 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指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z，

这就意味着，**从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点**。

也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。

让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。

动画如下：

![dc5304635c7db58394e409d0b315958f.gif][]

那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。

其实这种情况和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

[Link 1]: https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E5%88%A4%E6%96%AD%E9%93%BE%E8%A1%A8%E6%98%AF%E5%90%A6%E6%9C%89%E7%8E%AF
[2c0f70163dcef3f6a30a11eb1acc348e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/adef520f3b0d4f1d9c128b3f1f32b0d2.png
[ca63bdd842455d9a60adbb531c168f3b.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/de01c301a42f41da8c5d7eb2d318561b.gif
[Link 2]: https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E5%A6%82%E6%9E%9C%E6%9C%89%E7%8E%AF-%E5%A6%82%E4%BD%95%E6%89%BE%E5%88%B0%E8%BF%99%E4%B8%AA%E7%8E%AF%E7%9A%84%E5%85%A5%E5%8F%A3
[7ef1cc8306dbb7e5bcffe498028b4d79.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/41eb1c551e87476d844b4916cccfb9a3.png
[dc5304635c7db58394e409d0b315958f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/fc26049cfd81466aa497f03c82c5c5d7.gif