05
18

发表于 • • 被 227 人看爆

问题描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 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都是相交点。

分享到：