题目描述
一个链表中包含环,请找出该链表的环的入口结点。
解法一:
要想知道环的入口节点,则必须至少经过该节点两次,类似于“字符流中第一个只出现一次的字符”,可以记录之前的节点,每输入一个新节点则判断其出现的次数。
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
Set<ListNode> set = new HashSet<ListNode>();
while(pHead != null) {
if(!set.contains(pHead)) {
set.add(pHead);
}
else {
return pHead;
}
pHead = pHead.next;
}
return null;
}
}
解法二:
虽然解法一的时间复杂度为O(n),但是空间复杂度为O(n),考虑是否有办法减少空间复杂度。
这个问题可以分成几部分:
1、判断是否存在环。
可以设置两个指针,慢指针每次只一个节点,快节点每次移动两个节点,则经过若干次循环后,若存在环则快慢节点必有相遇的时刻,否则快指针会首先到达链表尾。
2、判断环中节点数。
当快慢指针相遇时,另快节点保持静止,慢节点继续遍历,当快慢节点再次相遇时,便可知道环中节点数count。
3、利用环中节点数找到换的入口节点。
只需要设置两个慢指针m、n,另n先移动count节点,然后m、n节点同时向前移动,当m和n相遇时,便是在环的入口节点。
时间复杂为O(n),空间复杂度O(1)
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead == null || pHead.next == null)
return null;
ListNode l1 = pHead;
ListNode l2 = pHead;
int count = 0;
do{
if(l2 == null) {
return null;
}
else {
l1 = l1.next;
l2 = l2.next.next;
}
}while(l1 != l2);
do{
count++;
l1 = l1.next;
}while(l1 != l2);
l1 = pHead;
l2 = pHead;
for(int i = 0; i < count; i++) {
l2 = l2.next;
}
while(l1 != l2) {
l1 = l1.next;
l2 = l2.next;
}
return l1;
}
}
解法三:
image与解法二相同,我们可以设两个快慢指针m、n,通过两个指针是否相遇来判断是否含有闭环。
但是当m和n相遇时,我们假设相遇点为B,环为顺时针,环总厂为c,环入口点到相遇点的长度为a,起点到环入口点的距离为x,m速度为n的两倍。则相遇时通过的总距离也为两倍:
Sm=2Sn
Sm=x+nc+a
Sn=x+mc+a
所以可以得到x=(n-2m-1)c+c-a
c-a为橙色部分。
所以我们可以令一个指针这时从起点出发,慢指针n继续前进,当两指针相遇时便为环的入口点。
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
ListNode l1 = pHead;
ListNode l2 = pHead;
int count = 0;
//检查l1和l2是否会相遇
do{
if(l2 == null) {
return null;
}
else {
l1 = l1.next;
l2 = l2.next.next;
}
}while(l1 != l2);
//设置从头出发的指针
l2 = pHead;
while(l1 != l2) {
l1 = l1.next;
l2 = l2.next;
}
return l1;
}
}
解法四:
断链法:
由于题目已经确定了链表中含有环,如果允许对输入进行修改的话,可以将链表逐步断链,最后剩下的节点便为环的入口节点。
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead){
if(pHead==null|| pHead.next==null) {
return null;
}
ListNode fast=pHead.next;
ListNode slow=pHead;
while(fast!=null){
slow.next=null;
slow=fast;
fast=fast.next;
}
return slow;
}
}
网友评论