• 🏡
    首页
  • 📎
    归档
  • ✍
    日志
  • 🐂
    留言板
顶 峰 相 见
顶 峰 相 见

dfxj

各自努力,顶峰相见

05月
18
算法

环形链表入口及其相交问题

发表于 2020-05-18 • 被 243 人看爆

问题描述
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

判断链表是否存在环

快慢指针

设置两个链表指针(fast, slow),初始值都指向链表头结点,然后两个指针都往前走,不同的是slow每次前进一步,fast每次前进两步,如果存在环,两个指针必定相遇。
show code

    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        ListNode fast = head;
        ListNode slow= head;
        while(fast!=null && slow!=null){
            slow = slow.next;
            fast = fast.next;
            if(fast==null){
                return false;
            }
            fast = fast.next;
            if(slow.equals(fast)){
                return true;
            }
        }
        return false;
    }

哈希表

如果我们用一个 Set 保存已经访问过的节点,我们可以遍历整个列表并返回第一个出现重复的节点。

找到环的入口点

思路如图

show code

 public ListNode detectCycle(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode fast = head;
        ListNode slow= head;
        ListNode ptr=null;
        while(fast!=null && slow!=null){
            slow = slow.next;
            fast = fast.next;
            if(fast==null){
                return null;
            }
            fast = fast.next;
            if(slow.equals(fast)){
                ptr = fast;//快慢指针环上交点
                break;
            }
        }
        ListNode ptr2 = head;
        while(ptr2!=null && ptr!=null){
            if(ptr.equals(ptr2)){
                return ptr;
            }
            ptr =ptr.next;
            ptr2=ptr2.next;
        }
        return null;
    }

扩展问题

  • 找出带环的两条链表相交的第一个节点

分两种情况:

  1. 只有一条链表带环,此时两条链表不可能相交;否则,由于相交结点后的所有结点由两条链表共享,因此导致另一条不带环的链表却出现环,导出相悖的结论。
  2. 两条链表都带环。如果两条链表相交,则他们共享同一个环!

带环链表相交,如图所示,存在两种情况:

  1. 交点在环中
  2. 交点不在环中

解决方法:
第一步:分别找出两个链表的环入口点pos1, pos2;
第二步:如果pos1==pos2, 属于第二种情况:交点不在环中。然后以pos1作为两条链表的终点,利用求不带环单链表交点的方法求出交点。
第三步:如果pos1!=pos2, 从pos1开始遍历环中的节点,如果没有发现有节点与pos2相等,则说明pos1、pos2不在同一个环上,说明两条链表没有交点,否则,存在交点。
第四步:pos1或者pos2都是相交点。

分享到:
双指针技巧总结
两个单链表相交的起始节点
  • 文章目录
  • 站点概览
dfxj

trade what you see, not what you think

Github QQ Email RSS
看爆 Top5
  • 金融交易技术分析 1,247次看爆
  • Angular 变更检测 —— 它到底是如何工作的? 1,211次看爆
  • kubernetes低版本java客户端ProcessorListener容量问题 1,117次看爆
  • Angular SSR踩坑记录 1,083次看爆
  • kubernetes容器编排和调度管理 1,011次看爆

站点已萌萌哒运行 00 天 00 小时 00 分 00 秒(●'◡'●)ノ♥

Copyright © 2021 dfxj