当前位置：首页 > news >正文

【数据结构】LinkedList与链表(1) + 经典面试OJ题解析 —— 有码有图有真相

news 2025/3/19 12:54:05

LinkedList与链表

1. ArrayList的缺陷

2. 链表的概念及结构

3. 链表的实现（单链表）

3.1 定义节点，内部类

3.2 打印链表(遍历链表)

【总结】

3.3 得到单链表的长度 O(N)

3.4 查找是否包含关键字key是否在单链表当中

3.5 头插法 O(1)

3.6 尾插法 O(N)

【结论】

3.7 任意位置插入，第一个数据节点为0号下标

3.8 删除第一次出现关键字为key的节点

3.9 删除所有值为key的节点（遍历一遍）

3.10 清空链表

4. 链表面试题

4.1 移除链表元素

4.2 反转链表(常考)

4.3 链表中间节点

4.4 输出倒数第k个节点

4.5 合并两个有序链表

4.6 链表的回文结构

4.7 链表分割

4.8 相交链表(常考)

4.9 环形链表(重点)

4.10 环形链表II(重点)

【快慢指针两种用法】

LinkedList与链表

1. ArrayList的缺陷

优点：

当给下标的时候，查找速度非常快。适合给定下标的查找，O(1)

缺点：

ArrayList底层使用连续的空间，任意位置插入或删除元素时(最坏情况在0下标位置)，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N)。
增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。为了能够解决这些问题，java集合中又引入了LinkedList，即链表结构。

2. 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

链表：类似火车一样他是由一个一个的节点/结点(车厢)组成的。

注意：

从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续。
现实中的节点一般都是从堆上申请出来的。
从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

链表是一个个叫做节点/结点的东西组成的，因此可以把节点定义为一个类(内部类)。

每一个数据节点都是由两部分组成的value域和next域。

节点的组织是通过当前这个节点它的next域存储下一个节点的地址。

不带头单向非循环链表，定义head引用代表当前链表的头节点(即第一个节点，随时可能变化)。
尾节点：它的next域是一个null 不指向任何节点

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

带头的链表，头节点里面的数据没有意义，无效的数据。
head就是一个头节点，删除12头节点不会改变，head 相当于火车头永远都是头节点；
不带头删除12，第一个节点变成了23，随时可能变化。

带头与不带头的区别：

不带头里面做的就是乘客车厢(相当于无人驾驶)，添加一个车厢(节点)可以放到乘客车厢最前面，哪个乘客在前面都一样。即不带头，第一个节点随时可能变化，但head永远指向第一个节点(头节点)。
带头的情况下头节点就是司机车厢(相当于火车头)，添加一个车厢(节点)不能在司机车厢前面，必须在司机车厢后面(永远不能取代司机的位置)，火车头永远都是头节点。即带了头，这个头节点永远都是第一个节点，head永远指向这个头节点。

重点掌握以下两种链表结构： 单向不带头非循环链表，双向不带头非循环链表

单向不带头非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多

双向不带头非循环链表：在Java的集合框架库中LinkedList底层实现就是双向不带头非循环链表。

至少有三个域：value数值域，prev前驱，next后继
head 永远指向双向链表的第一个节点
last 永远指向双向链表的最后一个结点

3. 链表的实现（单链表）

实现一个单向不带头非循环链表。定义一个接口IList里面有许多增删改查的方法（其实这个接口可有可无。接口是公共的行为规范标准），再定义一个类MySingleList实现这个接口并重写其中的方法。

3.1 定义节点，内部类

链表由一个一个节点组成，把节点起名为Node，即为Node类，因为每个链表中的节点都是由value域和next域构成的。即有两个成员属性。
把Node定义为内部类，即节点脱离链表这个类就没有存在的意义了，链表是由一个一个节点构成的，所以定义在链表中的内部类。
反面例子；class类中的老师和学生脱离学校，它们还能单独做一个类存在的。但是Node脱离链表就没有存在的意义了。
如果Node定义为静态内部类，那我们认为Node不需要外部类对象（链表），就可以单独存在，但是节点单独存在没有意义。
Node 加stastc，Node不依赖外部对象；Node 不加stastc，Node 依赖外部对象；
节点定义为静态内部类或实例内部类，看具体需求。

next域中存储的是下一个节点的地址，节点是一个对象，所以next类型应该是节点对象引用的类型。引用类型，默认值为null
提供带有一个参数的构造方法，为什么不提供两个？因为创建节点的时候你不知道next域中存储下一个节点的地址是什么，这个需要业务实现。next默认值为null
单向不带头非循环链表，提供一个haed引用代表当前链表的头节点，head属于链表的成员。

通过枚举，先手动创建一个链表，真正的链表并非这样创建的。

通过node1.next = node2;...... 把节点都串起来，这个时候通过node1就可以把串起来的节点都拿到。但是node1、node2、node3、node4都是createLink方法的局部变量，创建完链表之后就被回收了。如何拿到链表中所有节点。

【解决方法】

把createLink方法返回值变为ListNode，return node1;
或者让this.head = node1; head引用指向了node1引用所指向的对象。即head指向了node1指向的位置，通过head就能找到链表中所有的节点。

没有被引用指向的节点对象都会被回收。串起来后每个节点对象被前一个节点(前驱节点)next域中的引用(地址)指向着，第一个节点则定义一个ListNode类型的head引用变量指向它。
这样就能通过head找到所有的节点对象了，而node1, node2......这些局部变量(里面存储也是节点的地址)方法结束后就被回收了。
例如，创建一个人的对象，Preson preson = new Preson(); 如果preson被回收了，不再存储这个对象的地址，不再指向这个对象了，这个对象就被回收了。节点也是类，也能实例化对象。当引用变量被回收，不再存储这个节点对象地址，不再指向这个节点了，这个节点对象就被回收了。

3.2 打印链表(遍历链表)

【总结】

只要涉及到链表遍历，几乎都需要创建一个变量(cur)代替head，防止下次使用链表找不到头。
从一个节点，走到下一个节点：每次cur移动都是 cur = cur.next; 语句执行的。
cur != null 把整个链表的每一个节点，都遍历完成。走到了最后一个节点后面的位置，cur指向null。
cur.next != null 遍历到链表的尾巴。走到了最后一个节点得位置，cur指向最后一个节点。
修改当前节点的next值为指定的节点，node1.next = node2;

3.3 得到单链表的长度 O(N)

两种方法：

得到单链表的长度，遍历数组时间复杂度为O(N)
或者定义一个useSize为成员变量，在添加节点组成链表的时候，添加一个，useSize就增加1；或删一个减一个。时间复杂度就会被降为0(1)

public int size() {ListNode cur = this.head;int count = 0;while (cur != null) {count++;cur = cur.next;}return count;
}

3.4 查找是否包含关键字key是否在单链表当中

public boolean contains(int key) {ListNode cur = this.head;//遍历比较是否包含该keywhile (cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;
}

此时节点val域中的数据为int类型的，如果是引用类型或自定义类型不能用==比较，需要用equals
自定义类型比较的时候一定要重写equals方法

3.5 头插法 O(1)

当要插入节点的时候，实例化一个节点，插入到当前链表的第一个位置。

public void addFirst(int data) {ListNode node = new ListNode(data);//链表为空时if (head == null) {this.head = node;return;}node.next = this.head;this.head = node;
}

if语句后的两行代码，其实包含了链表为空的情况。可以不用if语句。
注意：如果写成head = node node.next = head 就会出现找不到后面节点的情况。

3.6 尾插法 O(N)

指的是将待插入的节点，存放在链表的最后一个位置。

实例化一个节点；遍历找尾巴 O(N)

注意判断是否空链表第一次尾插入，如果不判断 cur.next 可能会发生空指针异常。

public void addLast(int data) {Node node = new Node(data);//链表为空时if (this.head == null) {this.head = node;return;}ListNode cur = this.head;//寻找最后一个节点while (cur.next != null) {cur = cur.next;}cur.next = node;
}

【结论】

1、如果想让cur停在最后一个节点的位置 cur.next != null

2、如果想把整个链表的每个节点，都遍历完，那么就是 cur ! = null

3、头插法的时间复杂度O(1)；尾插法的时间复杂度O(N)

4、链表的插入，只需要改变指向就可以了。

3.7 任意位置插入，第一个数据节点为0号下标

链表其实是没有索引的，我们就只是把节点当做0索引 1索引，加不加没有关系。索引位置只是相对的。
插到哪个位置不能是找到这个位置，只能找到待插位置的前一个；因为插入的方法是 node.next = cur.next； cur.next = node；（cur为待插入位置的前一个节点，node是待插入节点）链表是单向的，如果走到要待插入的位置，就找不到前面的位置了，无法将节点插入。
所以该题的关键点就是找到cur的位置，也就是index-1的位置。如何找到，只需要让cur = cur.next 往前走 index-1 步就可以了。
如图：如果要插入intdex的位置，2的位置

在插入一个节点的时候，一定要先绑定后面这个节点。

private void checkIndex(int index) throws ListIndexOutOfException {if (index < 0 || index > size()) {throw new ListIndexOutOfException("任意位置插入下标不合法："+ index);}
}//任意位置插入,第一个数据节点为0号下标
@Override
public void addIndex(int index, int data) {checkIndex(index);//头插法if (index == 0) {addFirst(data);return;}//尾插法if (index == size()) {addLast(data);return;}//往中间位置任意插入ListNode cur = searchPrev(index);ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;
}//找到 index - 1 位置下标
private ListNode searchPrev(int index) {ListNode cur = this.head;int count = 0;//让cur 走index - 1 步while (count != index - 1) {cur = cur.next;count++;}return cur;
}

插入位置合法性异常类：

public class ListIndexOutOfException extends RuntimeException{public ListIndexOutOfException(String message) {super(message);}
}

3.8 删除第一次出现关键字为key的节点

删除第一次出现关键字为key时，不能让cur直接走到要删除的位置，只能在该位置的前一个位置。因为删除该位置时，需要将前一个位置节点与要删除位置后面的节点串起来，链表是单向的，无法再找到前一个节点了。(遍历一次链表前提下)。
利用 cur.next.val == key; 来找到要删除位置前一个节点。
如图，要删除的key为23

思路顺序：①->②->③，先寻找最基本最简单的情况构造出逻辑写出代码，然后慢慢完善特殊情况。

这里需要判断第一个节点是否是要删除的元素，因为第一个节点没有前驱，cur.next.val直接跳过了第一个节点，从第二个节点开始了。
删除时cur和del同时指向一个节点，del是局部变量，方法结束后就被回收掉，当del被回收之后就不会存储这个节点的地址，不再指向这个节点，这个节点就被回收了。

删除和任意位置插入，都需要拿到该节点的前驱。
绑定节点的时候一定先绑定后面的。

3.9 删除所有值为key的节点（遍历一遍）

思路：删除某个节点必须知道前一个节点是谁，即前驱节点是谁，否则这个节点不能删除。

设置两个快慢引用。cur代表当前需要删除的节点；prev是删除节点的前一个节点。

没引用的节点不用管，直接就被回收了，不用置空；在C中类似的要free置空。

有一个非常妙的方法，就是把该if语句放到最后面就可以了；因为写的代码是从第二个节点开始判断的，只有头没有处理，所以最后处理一下头就可以了。

public void removeAllKey(int key) {//判断链表是否为空if (head == null) {return;}/*while (head.val == key) {head = head.next;}*///准备一个快慢节点，用来记录前驱节点ListNode prev = head;ListNode cur = head.next;while (cur != null) {if (cur.val == key) {prev.next = cur.next;} else {prev = cur;}cur = cur.next;}//最后判断第一个节点的val值是否为keyif (head.val == key) {head = head.next;}
}

3.10 清空链表

两种方法：

如果value域中是基本类型。head = null；没有指向头节点，所以头节点被回收，下一个节点也是，没有指向，也被回收。也可以通过for循环一个一个置空。
如果value域中是引用类型。通过for循环的方法把每个节点value域和next域都置为null。

最后head需要手置空

public void clear() {//暴力置空//this.head = null;//ListNode cur = head;while (cur != null) {ListNode curNext = cur.next;cur.val = 0;cur.next = null;cur = curNext;}//手动置空headhead = null;
}

4. 链表面试题

4.1 移除链表元素

删除链表中等于给定值 val 的所有节点，与上面3.9 删除所有值为key的节点方法一样。OJ链接

OJ题在线判题系统（英语：Online Judge，缩写OJ）是一种在编程竞赛中用来测试参赛程序的在线系统，也可以用于平时练习。许多OJ网站会自发组织一些竞赛。

4.2 反转链表(常考)

反转一个单链表。OJ链接

思路：利用头插法进行反转，定义一个cur进行头插，并且再定义一个curNext记录cur.next；因为cur进行头插的时候cur的next值一定会改变。

时间复杂度O(n)，空间复杂度O(1)

public ListNode reverseList() {if (head == null) {return null;}//只有一个节点if (head.next == null) {return head;}ListNode cur = head.next;head.next = null;while (cur != null) {//curNext 记录cur中的nextListNode curNext = cur.next;cur.next = head;head = cur;cur = curNext;}return head;
}

指定节点位置打印：

/*** 这个是从指定位置开始打印* @param newHead*/
public void display(ListNode newHead) {//用一个变量代替newHead，防止找不到头(第一个节点)ListNode cur = newHead;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();
}

测试类：

public static void main(String[] args) {MySingleList mySingleList = new MySingleList();mySingleList.addLast(12);mySingleList.addLast(11);mySingleList.addLast(23);mySingleList.addLast(12);mySingleList.addLast(34);mySingleList.display();MySingleList.ListNode ret = mySingleList.reverseList();mySingleList.display(ret);
}
//执行结果
12 11 23 12 34 
34 12 23 11 12

4.3 链表中间节点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。OJ链接

第一种方法：

思想：利用快慢指针

快指针走两步，慢指针走一步，当快指针走终点的时候，慢指针一定是走到了中间的位置。同时出发，用时相同，速度是二倍关系，走的路程也一定是二倍关系。
如果fast走4步，slow走2步可不可以？不可以，如果节点个数不够就直接无了，会发生越界，一定会发生空指针异常，所有走一步和走两步是最好的选择。
(fast != null && fast.next != null)条件不能互换，因为fast 可能为null，如果互换了fast为null，就会发生空指针异常。

public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}return slow;
}

第二种方法：

先求整个链表的长度
再求长度/2 找到这个中间节点

public ListNode middleNode(ListNode head) {//1、求数组长度ListNode cur = this.head;int len = size();//2、求长度/2 找到这个中间节点//让cur走 长度/2 步for (int i = 0; i < len/2; i++) {cur = cur.next;}return cur;
}

4.4 输出倒数第k个节点

输入一个链表，输出该链表中倒数第k个结点。OJ链接

第一种方法：

可以让cur走 length - k步，此时cur的位置就是倒数第k个节点的位置。但是此方法相对简单，我们用另一种方法。

第二种方法：

思路：利用快慢指针，根据下图可知，慢指针slow与快指针fast相差 k-1步；即倒数第k个节点与最后一个节点之间的关系相差 k -1 步，所以slow的位置就是倒数第k个节点。我们利用这个关系，

先让fast走k-1步
fast 和slow开始同时一步一步走
当fast.next为空的时候，slow所指的位置就是倒数第k个

size()是求单链表的长度，也是遍历了一遍链表。我们对此代码进行优化：

public ListNode FindKthToTail(int k) {if (k <= 0 || head == null) {return null;}ListNode fast = this.head;ListNode slow = this.head;for (int i = 0; i < k - 1; i++) {fast = fast.next;//处理 K 太大的问题if (fast == null) {return null;}}while (fast.next != null) {fast = fast.next;slow = slow.next;}return slow;
}

4.5 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。OJ链接

思路：

两个链表的节点head1.val与head2.val比较，较小的值作为合并后新链表的头节点。创建一个虚拟节点记录这个头；
同时创建一个tmpH引用指向拼接时链表的最后一个节点；
通过循环比较两个链表的节点然后合并。

这里是mergeTwoLists方法合并两个有序链表，放在MySingleList类（一个链表）中不太合适，但是也并非不可以；

把mergeTwoLists方法的实现放到测试类（Test）中，创建两个有序链表，然后调用mergeTwoLists方法，实现两个有序链表的合并。

public class Test {//将两个有序链表合并为一个新的有序链表并返回。//新链表是通过拼接给定的两个链表的所有节点组成的。public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode head1, MySingleList.ListNode head2) {//虚拟节点，起标识作用MySingleList.ListNode newH = new MySingleList.ListNode(-1);MySingleList.ListNode tmpH = newH;while (head1 != null && head2 != null) {if (head1.val < head2.val) {tmpH.next = head1;head1 = head1.next;} else {tmpH.next = head2;head2 = head2.next;}tmpH = tmpH.next;}//上面代码走完head1、head2可能还有剩余节点需要拼接if (head1 != null) {tmpH.next = head1;}if (head2 != null) {tmpH.next = head2;}return newH.next;}
}

测试结果：

public static void main(String[] args) {MySingleList mySingleList1 = new MySingleList();mySingleList1.addLast(8);mySingleList1.addLast(12);mySingleList1.addLast(23);mySingleList1.addLast(45);mySingleList1.addLast(90);mySingleList1.display();MySingleList mySingleList2 = new MySingleList();mySingleList2.addLast(5);mySingleList2.addLast(11);mySingleList2.addLast(22);mySingleList2.addLast(25);mySingleList2.display();System.out.println("===========================");MySingleList.ListNode head = mergeTwoLists(mySingleList1.head, mySingleList2.head);mySingleList1.display(head);}
//执行结果
8 12 23 45 90 
5 11 22 25 
===========================
5 8 11 12 22 23 25 45 90

用指定节点位置打印（4.2反转链表处），这里哪个对象调用display方法打印都可以，因为指定的是从拼接后新链表头结点位置开始打印。

4.6 链表的回文结构

对于一个链表，请设计一个时间复杂度为O(n)，额外空间复杂度为O(1)的算法，判断其是否为回文结构。OJ链接
给定一个链表的头指针head，请返回一个boolean值，代表其是否为回文结构。保证链表长度小于等于900。测试样例：

思路：

找到中间节点。利用快慢指针，快指针走两步，慢指针走一步。
反转。反转中间节点后的半部分链表，利用头插法。
从前往后，从后往前。比较节点的val值。

怎么反转中间节点后半部分的链表？

在中间节点后边定义cur和curNext 两个引用。cur代表当前需要反转的节点，因为反转需要修改cur的next值，又因为为单向链表，
防止修改后的cur找不到下一个需要反转的节点，所以要用curNext先记录一下cur.next原来的值（也就是下一个节点）。然后开始移动slow，cur，curNext

这里注意一定是slow从后往前走，因为反转后slow一定指向最后一个节点，而fast可能不是指向最后一个节点。即偶数节点情况下fast指向最后节点的后面null。如上图所示

代码可以先完成处理奇数节点的情况，然后再完善处理偶数的情况。

处理偶数节点情况的 if 语句，一定是在判断两个val值相等if语句的后面。

public boolean chkPalindrome() {if (head == null) {return true;}if (head.next == null) {return true;}ListNode fast = head;ListNode slow = head;//1.找到中间节点 利用快慢指针while (fast!= null && fast.next != null) {fast = fast.next.next;slow = slow.next;}//2. 反转slow后面的链表 利用头插法ListNode cur = slow.next;while (cur != null) {ListNode curNext = cur.next;cur.next = slow;slow = cur;cur = curNext;}//3.从后往前 从前往后while (head != slow) {if (head.val != slow.val) {return false;}//偶数节点情况的判断if (head.next == slow) {return true;}head = head.next;slow = slow.next;}return true;
}

4.7 链表分割

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。OJ链接

思路：遍历原来的链表，（假设有两段）第一段放小于x的节点，第二段放大于或等于x的节点，线段中的节点采用尾插连接（用的还是原来的节点，没有实例化节点，没有创建新的链表，只是对链表本身的修改），不会改变原来的数据结构，最后两个向量串起来，返回重新排列后的链表头节点。
注意重新排列后的链表尾结点next一定要置为null，因为尾结点可能不是原来链表的尾结点，如果不置空会进入死循环。
两段不一定都同时存在。即有可能存在全部小于x或全部大于等于x的数据。可以能出现空指针异常，一定要判断。

be 和 ae 永远指向的是，最后一个节点。

public ListNode partition(ListNode head, int x) {if (head == null) {return null;}ListNode cur = head;ListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;while (cur != null) {if (cur.val < x) {// 判断小于 x 是否是第一次插入，用尾插法if (bs == null) {//插入第一个节点bs = cur;be = cur;} else {be.next = cur;//be永远指向的是 最后一个节点be = be.next;}} else {// 判断大于 x 是否是第一次插入，用尾插法if (as == null) {//插入第一个节点as = cur;ae = cur;} else {ae.next = cur;//ae永远指向的是 最后一个节点ae = ae.next;}}cur = cur.next;}//开始串起来//可能存在全部小于x 或全部大于等于x的数据if (bs == null) {//包含第一段为空和链表为空的情况return as;}//第一段不为空be.next = as;//走到这里be(第一段)一定不为空if (ae != null) {//这里需要判读一下第二段是否为空ae.next = null;}return bs;
}

4.8 相交链表(常考)

输入两个链表，找出它们的第一个公共结点。OJ链接

注意，相交的链表是Y 形状，不是X形状，因为节点地址只有一个，都指向了相交的节点

思路：

先遍历链表，两个链表长度相同，可以同时走，走到相交的节点（相遇），返回相交节点。
先遍历链表，两个链表长度不同，最长的链表先走相差的步数（相差的步数一定是在相交之前的节点个数），然后同时走一步一步走，走到相交的节点（相遇），返回相交节点。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pl = headA;ListNode ps = headB;int lenA = 0;int lenB = 0;//1. 遍历两个链表计算长度while (pl != null) {lenA++;pl = pl.next;}while (ps != null) {lenB++;ps = ps.next;}// 走到这里，如果没有进入下面if语句// pl和ps此时都为null,需要重新修正指向pl = headA;ps = headB;//相差的步数int len = lenA - lenB;if (len < 0) {//修正一下 pl和ps的指向pl = headB;ps = headA;len = lenB - lenA;}//代码执行到这里，len一定是正数//pl一定指向最长的链表，ps一定指向最短的链表//2. 让最长链表先走差值步while (len != 0) {pl = pl.next;len--;}//3. 同时开始一步一步走 4. 相遇就是相遇点//包含pl和ps都为null的情况while (pl != ps) {pl = pl.next;ps = ps.next;}//没有相交的情况if (pl == null) {return null;}return pl; //包含了没有相交的情况。
}

4.9 环形链表(重点)

给定一个链表，判断链表中是否有环。OJ链接贝壳面试题

思路：

利用快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置同时开始运行，
如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。

判断环的问题，其实就是数学上的"追击问题"（可以理解为）

public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;//有环一定会相遇if (fast == slow) {return true;}}return false;
}

【问题】为什么快指针每次走两步，慢指针走一步可以？

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度（相差一个环）。
此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走完一圈之前，快指针一定是能追上慢指针的，即相遇。
快指针一次走3步，走4步，...n步行吗？可能永远不相遇也可能相遇

4.10 环形链表II(重点)

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 NULL。OJ链接

思路：

让一个指针从链表起始位置开始遍历链表，同时让另一个指针从判断环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终相遇的地方就是入口点。

(N-1)C + Y = X

其中N值越大，表明环越小，fast走的圈数越多（此时的slow走的还是X的路程，还没有入环）；
N值越小，表明环越大，fast走的圈数越少，N的值最小是1，即fast最少走1圈，也就是上图左边的情况。

【注意】

1、当慢指针进入环时，快指针可能已经在环中绕了n圈了，n至少为1。

因为︰快指针先进环走到相遇点的位置，最后又在相遇点的位置与慢指针相遇

2、慢指针进环之后，快指针一定会在慢指针走一圈之内追上慢指针

因为︰慢指针进环后，快慢指针之间的距离最多就是环的长度，而两个指针在移动时，每次它们之间的距离都缩减一步，因此在慢指针移动一圈之前快指针肯定是可以追上慢指针的。

而快指针速度是慢指针的两倍，因此有如下关系是：

2*(X+(C-Y))= X+NC+(C-Y)

X+X+C+C-Y-Y =X+NC+C-Y

X+C-Y=NC

(N-1)C +Y = X（n为1,2,3,4....….n的大小取决于环的大小，环越小n越大）

极端情况下，假设n = 1，此时：X = Y

即：一个指针从链表起始位置运行，一个指针从相遇点位置绕环，每次都走一步，两个指针最终会在入口点的位置相遇。

public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;//有环一定会相遇if (fast == slow) {break;}}if (fast == null || fast.next == null) {return null;}//代码走到这一定有环slow = head;while (slow != fast) {fast = fast.next;slow = slow.next;}return fast;
}

【快慢指针两种用法】

走差值步，然后同时开始一步一步走。不同位置同时出发，时间相同(while循环)，速度相同，路程永远相差差值步。有环也永远相差差值步。例题，4.4、4.8
快指针一次走两步，慢指针一次走一步。同一位置同时出发(头节点处)，时间相同(while循环)，速度相差二倍，路程也相差二倍。有环快指针一定能追上慢指针。例题4.3、4.6、4.9、4.10

链表刷题链接：Leetcode OJ链接 + 牛客 OJ链接

好啦Y(^o^)Y，本节内容到此就结束了。下一篇内容一定会火速更新！！！

后续还会持续更新数据结构与算法方面的内容，还请大家多多关注本up，第一时间获取新鲜的知识。

如果觉得文章不错，别忘了一键三连哟！