目录
一，与链表相关的题目（2）
1.输入两个链表，找出它们的第一个公共节点
2.给定一个链表，判断链表中是否有环
3.给定一个链表，返回链表开始入环的第一个节点，若无则返回null
一，与链表相关的题目（2）
1.输入两个链表，找出它们的第一个公共节点
下面是两个相交的链表
此时要找两个链表的相交节点非常简单
只需要将两个链表的头节点分别向后移
当head1 == head2 时说明改节点是它们的相交节点
但当两个链表长度不一样的时候就会出现问题
遇到这种情况，一般会先求出两个链表的长度len1与len2，让长的那个链表走两链表的差值步（len1-len2）/（len2 - len1）
之后走相同步数直至相遇
代码示例：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode cur1 = headA;
ListNode cur2 = headB;
int count1 = 0;
int count2 = 0;
while (cur1.next != null) {
count1++;
cur1 = cur1.next;
}
cur1 = headA;
while (cur2.next != null) {
count2++;
cur2 = cur2.next;
}
cur2 = headB;
int dif = 0;
if (count1 >= count2) {
dif = count1 - count2;
while (dif != 0) {
cur1 = cur1.next;
dif--;
}
} else {
dif = count2 - count1;
while (dif != 0) {
cur2 = cur2.next;
dif--;
}
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
if (cur1 == cur2) {
return cur1;
} else {
return null;
}
}
}2.给定一个链表，判断链表中是否有环
【思路】
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。
public class Solution {
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.给定一个链表，返回链表开始入环的第一个节点，若无则返回null
上一题我们知道了怎么求一个链表是否有环，而其实这一题也不难。基于上一题的基础上，我们给出以下推导：
通过以上过程我们推导出头节点距入口处（x）其实是等于快指针和慢指针相遇点到入口处的距离（y）的，所有我们大可在这里再次令slow等于head，让fast和slow以相同的速度往后走，因为速度一样，路程一样，所有它们再次相遇的地方就一定是这个环的入口点
这里是当fast只比slow多走一圈的情况
而还存在的情况就是当环很小，而head距入口处又非常远时，fast就会为了等待x进入环而多走n圈
此时我们还可以根据上一题的思路就可以推导出以下公式：
可以发现，slow到入口点的距离（x）其实是等于转的圈数减一乘以圈的周长，再加上slow和fast的相遇点距入口点的距离（y）的，并且我们上一题的推导结果也符合该条公式。
此时代码就可以基于上一题的代码进行修改并书写：
public class Solution {
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) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
return null;
}
}
