每日一题《剑指offer》链表篇之链表中环的入口节点
链表中环的入口节点
难度：中等
描述
给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
数据范围
数据范围： 0n≤10000，1<=结点值<=10000
要求：空间复杂度 O(1)，时间复杂度 O(n)
举例
输入描述：
输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
返回值描述：
返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。
解题思路
方法一：双指针 根据题干，不说别的，我们能发现这道题需要完成两个任务：
- 判断链表是否有环。
- 在有环的链表中找到环的入口。
对于第一个任务，可以参考判断链表中是否有环，主要思想是利用环没有末尾NULL，后半部分一定是环，然后快慢双指针相遇就代表有环。
那我们现在假定已经是一个有环的链表了，那么这个链表中怎么找到环的入口呢？在慢指针进入链表环之前，快指针已经进入了环，且在里面循环，这才能在慢指针进入环之后，快指针追到了慢指针，不妨假设快指针在环中走了nnn圈，慢指针在环中走了mmm圈，它们才相遇，而进入环之前的距离为xxx，环入口到相遇点的距离为yyy，相遇点到环入口的距离为zzz。快指针一共走了x+n(y+z)+yx+n(y+z)+yx+n(y+z)+y步，慢指针一共走了x+m(y+z)+yx+m(y+z)+yx+m(y+z)+y，这个时候快指针走的倍数是慢指针的两倍，则x+n(y+z)+y=2(x+m(y+z)+y)x+n(y+z)+y=2(x+m(y+z)+y)x+n(y+z)+y=2(x+m(y+z)+y)，这时候x+y=(n−2m)(y+z)x+y=(n-2m)(y+z)x+y=(n−2m)(y+z)，因为环的大小是y+zy+zy+z，说明从链表头经过环入口到达相遇地方经过的距离等于整数倍环的大小：那我们从头开始遍历到相遇位置，和从相遇位置开始在环中遍历，会使用相同的步数，而双方最后都会经过入口到相遇位置这yyy个节点，那说明这yyy个节点它们就是重叠遍历的，那它们从入口位置就相遇了，这我们不就找到了吗？
实现代码（java）
方法一:
public class Solution { //判断有没有环，返回相遇的地方 public ListNode hasCycle(ListNode head) { //先判断链表为空的情况 if(head == null) return null; //快慢双指针 ListNode fast = head; ListNode slow = head; //如果没环快指针会先到链表尾 while(fast != null && fast.next != null){ //快指针移动两步 fast = fast.next.next; //慢指针移动一步 slow = slow.next; //相遇则有环，返回相遇的位置 if(fast == slow) return slow; } //到末尾说明没有环，返回null return null; } public ListNode EntryNodeOfLoop(ListNode pHead) { ListNode slow = hasCycle(pHead); //没有环 if(slow == null) return null; //快指针回到表头 ListNode fast = pHead; //再次相遇即是环入口 while(fast != slow){ fast = fast.next; slow = slow.next; } return slow; } }
学习完本题的思路你可以解决如下题目：
链表中倒数最后k个节点
难度：中等
描述
输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。
数据范围
数据范围：0≤n≤105，0≤ai≤109，0≤k≤109
要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(1)，时间复杂度 O(n)
举例
例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：
其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。
解题思路
方法一:快慢双指针 我们无法逆序遍历链表，就很难得到链表的倒数第k个元素，那我们可以试试反过来考虑，如果当前我们处于倒数第k的位置上，即距离链表尾的距离是k，那我们假设双指针指向这两个位置，二者同步向前移动，当前面个指针到了链表头的时候，两个指针之间的距离还是k。虽然我们没有办法让指针逆向移动，但是我们刚刚这个思路却可以正向实施。
具体做法：
- step 1：准备一个快指针，从链表头开始，在链表上先走k步。
- step 2：准备慢指针指向原始链表头，代表当前元素，则慢指针与快指针之间的距离一直都是k。
- step 3：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数k个元素的位置。
方法二:先找长度再找最后k链表不能逆向遍历，也不能直接访问。但是对于倒数第k个位置，我们只需要知道是正数多少位还是可以直接遍历得到的。
具体做法：
- step 1：可以先遍历一次链表找到链表的长度。
- step 2：然后比较链表长度是否比k小，如果比k小返回一个空节点。
- step 3：如果链表足够长，则我们从头节点往后遍历n−k次即可找到所求。
实现代码（java）
方法一:
import java.util.*; public class Solution { public ListNode FindKthToTail (ListNode pHead, int k) { int n = 0; ListNode fast = pHead; ListNode slow = pHead; //快指针先行k步 for(int i = 0; i < k; i++){ if(fast != null) fast = fast.next; //达不到k步说明链表过短，没有倒数k else return slow = null; } //快慢指针同步，快指针先到底，慢指针指向倒数第k个 while(fast != null){ fast = fast.next; slow = slow.next; } return slow; } }
方法二:
import java.util.*; public class Solution { public ListNode FindKthToTail (ListNode pHead, int k) { int n = 0; ListNode p = pHead; //遍历链表，统计链表长度 while(p != null){ n++; p = p.next; } //长度过小，返回空链表 if(n < k) return null; p = pHead; //遍历n-k次 for(int i = 0; i < n - k; i++) p = p.next; return p; } }
两个链表的第一个公共节点
难度：中等
描述
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
数据范围
数据范围： 0n≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)
举例
例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：
可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
解题思路
方法一:双指针长度比较法 如果两个链表有公共节点，那么它们后半部分都是相同的，我们要找的也就是后半部分的第一个节点。链表前半部分不同，长度也可能不同，因此同时遍历的话不一定就会同时到达第一个公共节点。
但是，如果我们能够找到长度差：
| 1 | intn = p1 - p2; |
较长的链表指针先走nnn步：
//假设pHead1更长 for(int i = 0; i < n; i++) pHead1 = pHead1.next;
然后两个指针分别走剩余的步数，就会同时到达第一个公共节点。
具体做法：
- step 1：单独的遍历两个链表，得到各自的长度。
- step 2：求得两链表的长度差nnn，其中较长的链表的指针从头先走nnn步。
- step 3：两链表指针同步向后遍历，遇到第一个相同的节点就是第一个公共节点。
方法二:双指针连接法 由上种方法长度差的思路，不同于上述一个指针先走另一个指针后走，仅需将两个链表连在一起，两个指针同步走。
p1 = p1 == NULL ? pHead2 : p1->next; p2 = p2 == NULL ? pHead1 : p2->next;
易知将两个链表连在一起长度都相等，对于遍历两个链表的两个指针，公共部分走的步数是一样的，非公共部分因都走了两个链表，因此也是相同的，所以绕了一圈，第一个相同的节点便是第一个公共节点。
具体做法：
- step 1：判断链表情况，其中有一个为空，则不能有公共节点，返回null。
- step 2：两个链表都从表头开始同步依次遍历。
- step 3：不需要物理上将两个链表连在一起，仅需指针在一个链表的尾部时直接跳到另一个链表的头部。
- step 4：根据上述说法，第一个相同的节点便是第一个公共节点。
实现代码（java）
方法一:
public class Solution { //计算链表长度的函数 public int ListLenth(ListNode pHead){ ListNode p = pHead; int n = 0; while(p != null){ n++; p = p.next; } return n; } public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { int p1 = ListLenth(pHead1); int p2 = ListLenth(pHead2); //当链表1更长时，链表1指针先走p1-p2步 if(p1 >= p2){ int n = p1 - p2; for(int i = 0; i < n; i++){ pHead1 = pHead1.next; } //两个链表同时移动，直到有公共节点时停下 while((pHead1 != null) && (pHead2 != null) && (pHead1 != pHead2)){ pHead1 = pHead1.next; pHead2 = pHead2.next; } } //反之，则链表2先行p2-p1步 else{ int n = p2 - p1; for(int i = 0; i < n; i++){ pHead2 = pHead2.next; } //两个链表同时移动，直到有公共节点时停下 while((pHead1 != null) && (pHead2 != null) && (pHead1 != pHead2)){ pHead1 = pHead1.next; pHead2 = pHead2.next; } } return pHead1; } }
方法二:
public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { //其中有一个为空，则不能有公共节点，返回null if(pHead1 == null || pHead2 == null) return null; ListNode p1 = pHead1; ListNode p2 = pHead2; //相当于遍历两次两个链表所有值 while(p1 != p2){ p1 = p1 == null ? pHead2 : p1.next; p2 = p2 == null ? pHead1 : p2.next; } return p1; } }
