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

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

# 算法 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×