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

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、环形链表精髓：

主要考察两知识点：

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

#判断链表是否有环

可以使用快慢指针法，分别定义 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重合。

动画如下：

#如果有环，如何找到这个环的入口

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

假设从头结点到环形入口节点 的节点数为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指针在环形里转了一圈之后，就遇到了 slow指针了。

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

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

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

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

动画如下：

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

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