题解 | #链表中环的入口结点#

链表中环的入口结点

http://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4

题目：链表中环的入口结点

输入描述：输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台将这2个会组装成一个有环或者无环单链表

返回值描述：返回链表的环的入口结点即可。而我们后台程序会打印这个节点

示例1：输入：{1,2},{3,4,5}，返回值：3

说明：返回环形链表入口节点，我们后台会打印该环形链表入口节点，即3

解法一：

思路分析：正常情况下，在判断是否有环的存在，我们可以设定两个速度不同的物体，让他们同时从同一地点出发，如果相遇则证明有环，反之不存在环，则速度不同的物体从同一地点出发不一定相遇，因此，可定义两个指针fast和slow，令两个指针以不同速度活动，最终判断是否相遇。

在是否能相遇的问题上，假设让一个指针从头节点开始，另一个指针从相遇结点开始，并以相同速度向后指，再次相遇的地方就是环的入口结点。

假设存在环，fast以速度2运行，slow以速度1运行，在slow走到入口t时，（m1为在slow首次到t时fast的位置，a为h到t的距离，b为t到m1的距离，n为环的周长）

具体C++代码如下所示：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if ( !pHead ) {//特殊情况
            return NULL;
        }
        ListNode *fast = pHead, *slow = pHead;
        while(fast && fast->next) {
            slow = slow->next;//慢
            fast = fast->next->next;//快
            if(slow == fast) {
                slow = pHead;//重新让slow从开头走
                while(slow - fast) {//相遇停止
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return NULL;
    }
};

访问所有的结点的同时，判断fast和slow指针，其时间复杂度为O(n)，空间复杂度为O(1)。

解法二：

思路分析：在思考数学问题的同时，我们也可以遍历单链表中的每一个结点，如果当前结点没有出现在设定的集合当中，则将其存入进去，否则，出现在当前集合当中，则当前结点就是环的入口结点。

实例分析：输入：{1,2},{3,4,5}，因为第一个为集合{1，2}，第二个集合为循环链表，所以将所有的元素存入一个统一的集合当中。

1，2	3，4，5
首先设定一个单链表set，将所有的元素存进去
1，2，3，4，5
第一个循环为3，所以3为起始结点

具体java代码如下所示：

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;
 
    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
 
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        Setset = new HashSet<>();
        while(pHead != null){
            if(set.contains(pHead)){
                return pHead;
            }
            else{
                set.add(pHead);
                pHead = pHead.next;
            }
        }
        return null;
    }
}

该算法需要一直判断pHead != null，故时间复杂度为O(n)，空间复杂度为O(n)。

算法自然分析文章被收录于专栏

在解决问题的同时，不断与人交流学习，通过牛客各式各样的题目，学习分享。