判断单链表中是否有环/两列表是否相交系列问题及C++实现

题目:

1.给一个单链表,判断其中是否有环的存在;
2.如果存在环,求出环上节点的个数;
3.如果存在环,找出环的入口点;
4.如果存在环,求出链表的长度;
5.如果存在环,求出环上距离任意一个节点最远的点(对面节点);
6.(扩展)如何判断两个无环链表是否相交;
7.(扩展)如果相交,求出第一个相交的节点;

解答:

1.给一个单链表,判断其中是否有环的存在;

  • 运用快慢指针来确定:每次快指针走两步,慢指针走一步。
  • 如果快慢指针重合,则代表链表有环(如果链表有环,则快指针将一直在环中绕圈,当慢指针进入环中时,速度不一样的两个指针必然重合)
  • 如果在快指针走到链表尾部(快指针指向NULL或下一个节点为NULL)。则代表没有环。(如果链表有环,则不会出现NULL节点)

2.如果存在环,求出环上节点的个数;

  • (接1问继续)快指针不动,慢指针继续前进。当快慢指针重合时,慢指针走的步数就是环上节点个数。(因为此时两个指针都在环上)

3.如果存在环,找出环的入口点;

  • 方法一:由2可知环的长度r。重新用两个指针在链表头部开始遍历。快指针先走r步,然后快慢指针同时一步一步走,当快慢指针重合时,重合点就是环的入口点,此时慢指针走的步数就是环外链表的节点数。(因为快指针一直比慢指针快r步,而环的长度也是r,所以慢指针刚进入环的入口时,快慢指针必然重合)
  • 方法二:只让快指针从链表头部重新走,慢指针在1中重合位置。此时两个指针同时一步一步走,重合点就是环的入口节点。此时慢指针走的步数就是环外链表的节点数。((盗图的,不要看快慢指针位置)假设问题1中快慢指针在m1出重合,假设单链表的头结点到环入口的距离为a,环入口到快慢指针相遇的结点距离为b,环的长度为r,慢指针总共走了s步,则快指针走了2s步。另外,快指针要追上慢指针的话快指针至少要在环里面转了一圈多(假设转了n圈加b的距离),得到以下关系:
        s = a + b
        2s = a + nr + b
        =>a + x = nr
        =>a = nr – b (n>=1)= (n-b) + (n-1)r)。


《判断单链表中是否有环/两列表是否相交系列问题及C++实现》

4.如果存在环,求出链表的长度;

  • 2问求出环的长度;3问求出环外部分长度,两个相加就是链表的长度。

5.如果存在环,求出环上距离任意一个节点最远的点(对面节点);

  • 在此节点设两个指针(快慢指针),快指针一次走两步,慢指针一次走一步。当快指针或快指针的下一个节点是起始位置时,此时慢指针的位置就是距离起始节点最远的节点。

6.(扩展)如何判断两个无环链表是否相交;

  • 方法一:分别遍历两个链表,找到链表中最后一个节点。如果相交,则两个链表的最后一个节点必然相等。
  • 方法二:将其中一个链表变成环,模仿前面几问,具体看下面7的解答。

7.(扩展)如果相交,求出第一个相交的节点;

  • 假设有两个链表listA和listB,如果两个链表都无环,并且有交点,那么我们可以让其中一个链表(不妨设是listA)的尾节点连接到其头部,这样在listB中就一定会出现一个环。因此我们将问题6和7分别转化成了问题1和2,具体看图:

《判断单链表中是否有环/两列表是否相交系列问题及C++实现》

代码:

ListNode EntryNodeOfLoop(ListNode h){  
        if(h == null || h.next == null)  
            return null;  
        ListNode slow = h;  
        ListNode fast = h;  
        while(fast != null && fast.next != null ){  
            slow = slow.next;  
            fast = fast.next.next;  
            if(slow == fast){  
                ListNode p=h;  
                ListNode q=slow;//相当于让q指向了m1  
                while(p != q){  
                    p = p.next;  
                    q = q.next;  
                }  
                if(p == q)  
                    return q;  
                }  
        }  
        return null;  
}

    原文作者:C后台开发从入门到就业
    原文地址: https://blog.csdn.net/lingfeng2019/article/details/80512633
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞