阿里面试真题详解:带环链表 II-阿里云开发者社区

开发者社区> 算法编程> 正文
登录阅读全文

阿里面试真题详解:带环链表 II

简介: 阿里面试真题详解:带环链表 II

描述
给定一个链表,如果链表中存在环,则返回到链表中环的起始节点,如果没有环,返回null。

在线评测地址:领扣题库官网

输入:null,no cycle
输出:no cycle
解释:
链表为空,所以没有环存在。
样例2
输入:-21->10->4->5,tail connects to node index 1
输出:10
解释:
最后一个节点5指向下标为1的节点,也就是10,所以环的入口为10。

算法思路:

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up: Can you solve it without using extra space?
考点:

  • 双指针链表判环
    题解:
  • 使用双指针判断链表中是否有环,慢指针每次走一步,快指针每次走两步,若链表中有环,则两指针必定相遇。
  • 假设环的长度为l,环上入口距离链表头距离为a,两指针第一次相遇处距离环入口为b,则另一段环的长度为c=l-b,由于快指针走过的距离是慢指针的两倍,则有a+l+b=2*(a+b),又有l=b+c,可得a=c,故当判断有环时(slow==fast)时,移动头指针,同时移动慢指针,两指针相遇处即为环的入口。

    /**
    * Definition for ListNode.
    * public class ListNode {
    *     int val;
    *     ListNode next;
    *     ListNode(int val) {
    *         this.val = val;
    *         this.next = null;
    *     }
    * }
    */ 
    public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next==null) {
            return null;
        }
    
        ListNode fast, slow;
        fast = head.next;                        //快指针
        slow = head;                                //慢指针
        while (fast != slow) {                //快慢指针相遇
            if(fast==null || fast.next==null)
                return null;
            fast = fast.next.next;
            slow = slow.next;
        } 
    
        while (head != slow.next) {  //同时移动head和慢指针
            head = head.next;
            slow = slow.next;
        }
        return head;                                //两指针相遇处即为环的入口
    }
    }

    更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接