V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hakunamatata11
V2EX  ›  推广

[LintCode 题解] 腾讯面试算法题:带环链表 II

  •  
  •   hakunamatata11 · 2020-03-17 18:29:00 +08:00 · 826 次点击
    这是一个创建于 1550 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目描述

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

    样例 1:

    输入:null,no cycle
    输出:no cycle
    解释:
    链表为空,所以没有环存在。
    
    

    image.gif

    样例 2:

    输入:-21->10->4->5,tail connects to node index 1
    输出:10
    解释:
    最后一个节点 5 指向下标为 1 的节点,也就是 10,所以环的入口为 10。
    

    image.gif

    题解

    考点:

    • 双指针链表判环

    题解:

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

    算法面试高频题班免费试听,攻略还有更多大厂常考题型。

    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;				//两指针相遇处即为环的入口
        }
    }
    

    image.gif

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2770 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 03:09 · PVG 11:09 · LAX 20:09 · JFK 23:09
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.