首页 > 试题广场 >

链表中环的入口节点

[编程题]链表中环的入口节点
  • 热度指数:134758 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
对于一个给定的链表,返回环的入口节点,如果没有环,返回null
拓展:
你能给出不利用额外空间的解法么?


说明:本题目包含复杂数据结构ListNode,点此查看相关信息
推荐
思路:
1)同linked-list-cycle-i一题,使用快慢指针方法,判定是否存在环,并记录两指针相遇位置(Z);
2)将两指针分别放在链表头(X)和相遇位置(Z),并改为相同速度推进,则两指针在环开始位置相遇(Y)。

证明如下:
如下图所示,X,Y,Z分别为链表起始位置,环开始位置和两指针相遇位置,则根据快指针速度为慢指针速度的两倍,可以得出:
2*(a + b) = a + b + n * (b + c);即
a=(n - 1) * b + n * c = (n - 1)(b + c) +c;
注意到b+c恰好为环的长度,故可以推出,如将此时两指针分别放在起始位置和相遇位置,并以相同速度前进,当一个指针走完距离a时,另一个指针恰好走出 绕环n-1圈加上c的距离。
故两指针会在环开始位置相遇。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL){
            return 0;
        }
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != NULL && fast->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                break;
            }
        }
        if(fast == NULL || fast->next == NULL){
            return NULL;
        }
        slow = head;
        while(slow != fast){
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

编辑于 2016-08-07 13:48:35 回复(51)
public ListNode detectCycle(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(slow==fast){
                slow=head;
                while(fast!=slow){
                    slow=slow.next;
                    fast=fast.next;
                }
                return slow;
                }
        }
        return null;
    }

发表于 2021-05-25 17:25:30 回复(0)

求助:为啥对快指针的赋值需要从第二个开始?
如果我对快慢指针的赋值是:

        ListNode slow = head.; // 慢指针
        ListNode fast = head.next; // 快指针

就提示运行超时,但是如果是下面的这种就是可以的。这是为啥啊?求大佬指点一下!
下面这个代码是可以通过的

    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode slow = head.next; // 慢指针
        ListNode fast = head.next.next; // 快指针
        while(fast != null && fast.next != null){
            if(fast == slow) { //有环
                while(head != slow){ //从头再来
                    head = head.next;
                    slow = slow.next;
                }
                return head;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return null;
    }
发表于 2021-05-08 13:28:07 回复(0)
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null || head.next==null) return null;
        ListNode l1=head,l2=head;
        int i=0;
        while(l2!=null && l2.next!=null){
            l1=l1.next;
            l2=l2.next.next;
            i++;
            if (l1==l2){
                l1=head;
                while(l1!=l2){
                    l1=l1.next;
                    l2=l2.next;
                }
                return l1;
            }
        }
        return null;
    }
}
双指针
发表于 2021-04-17 14:47:07 回复(0)
public class Solution {
    public ListNode detectCycle(ListNode head) {
    	if (head == null) {
    		return null;
    	}
    	//判断是否有环
    	ListNode meetNode = meetingNode(head);
    	if (meetNode == null) {//说明无环
    		return null;
    	}
    	//计算环的大小
    	ListNode fast = meetNode;
    	ListNode slow = meetNode;
        int roll=0;
        do {
        fast = fast.next;
            roll++;
        }while (slow != fast);
        //fast先走roll-1步,然后shlow走,直到他们相遇,即为入口
        slow = head;
    	fast = head;
        while(roll>0)
        {
            roll--;
            fast=fast.next;
        }
    	while (slow != fast) {
    		slow = slow.next;
    		fast = fast.next;
    	}
    	
     	return slow;
    }
    
    //寻找相遇节点,如果无环,返回null
    public ListNode meetingNode(ListNode head) {
    	ListNode slow = head;
    	ListNode fast = head;
    	while (fast != null && fast.next != null) {
    		slow = slow.next;
    		fast = fast.next.next;
    		if (slow == fast) {
    			return slow;
    		}
    	}
    	return null;
    }
}

分为三步:
1. 判断是否有环;
2. 计算环的大小数目
3. 快慢指针都归0,快指针先走环的数目k步,然后一起走,直到相遇,则为入口

发表于 2021-04-04 14:30:06 回复(0)
如上述的很多的图一样
这里涉及到一点数学和逻辑小技巧
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null)
            return null;
        ListNode meetNode=meetingNode(head);
        if(meetNode==null)return null;
        
        ListNode fast=head;
        ListNode low=meetNode;
        while(fast!=low){
            fast=fast.next;
            low=low.next;
        }
        return low;
    }
    
    public ListNode meetingNode(ListNode head){
        ListNode fast=head;
        ListNode low=head;
        while(fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            low=low.next;
            if(low==fast)return low;
        }
        return null;
    }
}


发表于 2021-04-02 12:15:26 回复(0)
这个思路是不是有点傻,哈哈哈,直接上HashSet,不过空间复杂度多了点。
import java.util.*;
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        Set<ListNode> set = new HashSet<>();
        set.add(head);
        while (head.next!= null) {
            head = head.next;
            if (set.contains(head)){
                return head;
            }
            set.add(head);
        }
        return null;
    }
}


编辑于 2021-03-27 11:42:39 回复(0)
环儿的入口结点:从head起,第一个在环儿里的结点。

思路:爱的暴力转圈圈,时间复杂度O((n-m)*m),n=链表长度,m=环的长度;最坏接近O(n^2)

    1)定义一对快慢指针,先让两个指针进入环中。
    若指针走的过程中转角遇到空null结点,说明没有环,return null即可。唉!没找到爱的圈圈。
    
    2)两个指针进入环中相遇后,进入下一步找环入口操作:
    从head依次往后枚举判断当前枚举的结点是否在环中,判断方法:
    让环中指针在环内转圈,若途中遇到了当前枚举的结点,说明该结点在环中。
    找到第一个这样的结点就是入口结点。
public ListNode detectCycle(ListNode head) {
        if(head!=null){
            ListNode first=head,second=head.next,start;//定义指针
            //尝试把指针拉入环中
            while(first!=second){
                if(first==null||second==null||second.next==null) return null;//没环
                first=first.next;
                second=second.next.next;
            }
            //有环
            //找环入口:从head起依次往后枚举,第一个在环里的结点就是环的入口结点
            start=second;//标记环起点
            first=head;
            while(first!=null){
                //second指针在环里转一圈,查看当前结点first是否在环里
                do{
                    if(second==first) return first;//找到的第一个就是结果
                    second=second.next;
                }while(second!=start);//转一圈退出
                first=first.next;//枚举下一个
            }
            return null;
        }
        return null;
    }

编辑于 2021-03-27 11:39:59 回复(0)
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                slow = head;
                while(slow!=fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
              break;
            }
        }
        if(fast.next == null || fast.next.next == null){ return null;}
        return slow;
    }
}


编辑于 2021-03-23 10:42:29 回复(0)
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // first get the length of the circel
        // use fast and slow pointer
        //how to get the length?first meet the try again count
        if(head == null||head.next == null) return null;
        int len = 1;
        ListNode slow = head;
        ListNode fast = head.next;
        ListNode temp;
        ListNode res = head;
        while(slow!=null&&fast!=null){
            slow = slow.next;
            fast = fast.next;
            if(fast!=null){
                fast = fast.next;
            }
            if(fast == slow) break;
        }
        if(fast==null||slow==null) return null;
        temp = slow;
        while(slow.next!=temp){
            slow = slow.next;
            len++;
        }
        for(int i = 0;i<len;i++){
            res = res.next;
        }

        while(head!=res){
            head = head.next;
            res = res.next;
        }
        return res;
    }
}
发表于 2021-03-19 00:01:17 回复(0)
//思路:和判断是否有环解法一致,将遍历后的节点指向一个新增节点,如果遍历过程中,某个节点指向了那个节点,那么这个节点就是入口节点(即交叉点)。

public static ListNode detectCycle(ListNode head) {         ListNode target = new ListNode(-1);         ListNode cur = head;         while(cur != null) {             if(cur.next == target) {                 return cur;             }             ListNode next = cur.next;             cur.next = target;             cur = next;         }         return null;     }

发表于 2021-03-08 15:26:53 回复(0)
 public ListNode detectCycle(ListNode head) {
        if (head==null) return null;
        //1.使用快慢指针方法,判定是否存在环
        //2.将两指针分别放在链表头(X)和相遇位置(Z),并改为相同速度推进,则两指针在环开始位置相遇(Y)。
        //3.证明:首先a是起点到环的距离 b是环起点到相遇点的距离 c是相遇点到环起点的距离
        //2*(a + b) = a + b + n * (b + c); a=(n - 1) * b + n * c = (n - 1)(b + c) +c;
        //即a = c; 下面i是慢指针 j是快指针 不涉及插入 所以不用设置哑头节点
        ListNode i = head,j = head;
        //j.next.next存在前提j.next存在 再者 要判断链表是否有尽头 仅仅看j下一步是不是空即可 i走的慢可以不管
        while (j.next!=null&&j.next.next!=null){
            //不能一上来就移动 这样i==j直接触发了 gg
            //不相等就快慢指针 分别行动直到i==j相遇再进行相应处理
            i = i.next;
            j = j.next.next;
            if (i==j) {
                ListNode temp = head;
                //i和j点相遇
                //起点位置和环位置同时每次走一步 一定会在环起点相遇 上面证明了a=c
                while (temp!=i){
                    temp = temp.next;
                    i = i.next;
                }
                //指向头节点的指针和指向相遇点的指针都相等了 说明在环起点相遇了 返回相遇节点值
                return temp;
            }
           
        }
        return null;
    }

发表于 2021-03-07 05:35:43 回复(0)
/**
思路:
假定快慢指针,相同时间下,快指针所走路程是慢指针的两倍
当两个指针在环上相遇时,快指针比慢指针多走了n圈
减去二者在环上重叠的部分,快指针多走的距离即是直线的长度;
故此时只需要将慢指针从头走起,快指针变为慢指针继续前进,二者定会在环入口相遇
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode p1 = head;
        ListNode p2 = head;
        int step = 0;
        do {
           step++;
           p1 = p1.next;
           p2 = p2.next.next;
        } while (p1 != p2 && p2 != null && p2.next != null);
        
        if (p2 == null || p2.next == null) {
            return null;
        }
        
        p1 = head;
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}

发表于 2021-01-31 15:00:48 回复(0)
public class Solution {
    public ListNode detectCycle(ListNode head) {
      if(head==null)  return null;
      while(head.next!=null){
          if(head.next==head) return head;
          ListNode r=head.next;
          head.next=head;
          head=r;
      }
        return null;
    }
}

/**
假设X,Y,Z分别为链表起始位置,环开始位置和两指针相遇位置,则根据快指针速度为慢指针速度的两倍,可以得出:
2*(a + b) = a + b + n * (b + c);即
a=(n - 1) * b + n * c = (n - 1)(b + c) +c;
注意到b+c恰好为环的长度,故可以推出,如将此时两指针分别放在起始位置和相遇位置,并以相同速度前进,当一个指针走完距离a时,另一个指针恰好走出 绕环n-1圈加上c的距离。
故两指针会在环开始位置相遇。
 */

public class Solution {
    public ListNode detectCycle(ListNode head) {
     if(head==null)  return null;
      ListNode slow=head;
      ListNode fast=head;
      while(fast!=null&&fast.next!=null){
          slow=slow.next;
          fast=fast.next.next;
          if(slow==fast){//相遇位置
            while(head!=slow){
                head=head.next;
                slow=slow.next;
            }
              return head;
              
          }
      }
        return null;
    }
}

编辑于 2021-04-02 09:02:18 回复(0)
发表于 2020-11-27 12:11:59 回复(0)
不求甚解双指针,如果转N圈就不理解了,1圈还好说。
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        ListNode ret=head;
        while(fast!=null){
            fast=fast.next;
            if(fast==null)return null;
            fast=fast.next;
            slow=slow.next;
            if(fast==slow){
                while(true){
                    if(ret==slow)return ret;
                    ret=ret.next;
                    slow=slow.next;
                }
            }
        }
        return null;
    }
}
发表于 2020-11-07 18:19:43 回复(0)
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null) return null;
        ListNode fast = head;
        ListNode slow = head;
        //先找出相遇的位置
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            //相遇了则跳出,此时slow==fast相遇
            if(slow==fast) break;
        }
        //不相等说明无循环
        if(fast!=slow) return null;
        //慢指针重新指向首部,快指针指向相遇节点,再次循环(速度一致)
        //再次相遇时是在循环的入口节点
        slow = head;
        while(slow!=fast){
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

编辑于 2020-09-26 23:24:38 回复(0)
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
// 思路:先判断有没有环。在有环的情况下,再找环的入口。
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode fast, slow;
        fast = slow = head;
        boolean flag = false;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                flag = true;
                break;
            }
        }
        if(flag == false){
            return null;
        }
        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

发表于 2020-09-01 10:55:44 回复(0)
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
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) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while (fast != null && slow != null) {
            if (fast == slow) {
                return fast;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return null;
    }
}

思路如下:
1. 首先使用快慢指针,判断是否有环,无环则直接返回null;
2. 在有环的情况下,将慢指针重新指向头部,然后两个指针每次均移动1位,最终相遇点就是环的入口。
第2步证明:

发表于 2020-08-29 07:02:42 回复(0)
利用快慢指针移动;快指针每次移动两次,慢指针移动一次;如果快慢指针不相等直到快指针为null 则判断无环;否则相等后;快指针指向头结点,快慢指针依次移动依次,知道相遇即为入口节点;代码如下:
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode slow=head,fast=head;
        while(fast.next!=null && fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                ListNode cur = head;
                while(cur!=slow){
                    cur=cur.next;
                    slow=slow.next;
                }
                return cur;
            }
        }
        return null;
    }
}


发表于 2020-08-24 01:11:00 回复(0)
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null)return null;
        ListNode next = head;
        //当上级节点离首节点的距离大于下级节点离首节点的距离时,此下级节点即为环的入口。
       int preD = d(head,next);
        while(next.next!=null){
             int nextD = d(head,next.next);
             if(preD>=nextD)return next.next;
             preD = nextD;
             next = next.next;
        }
        return null;
    }
    //返回节点和首节点的距离
    public int d (ListNode head,ListNode node){
        int d =0;
        ListNode temp = head;
        while(true){
            if(temp!=node){
                temp = temp.next;
                d++;
            }else{
                break;
            }
        }
        return d;
    }
    
    
    
}
发表于 2020-08-12 18:56:25 回复(0)