《剑指offer》链表中环的入口结点-ag真人游戏

题目描述

一个链表中包含环，请找出该链表的环的入口结点。

解题思路

可以用两个指针来解决这个问题。先定义两个指针p1和p2指向链表的头结点。如果链表中的环有n个结点，指针p1先在链表上向前移动n步，然后两个指针以相同的速度向前移动。当第二个指针指向的入口结点时，第一个指针已经围绕着揍了一圈又回到了入口结点。

以下图为例，指针p1和p2在初始化时都指向链表的头结点。由于环中有4个结点，指针p1先在链表上向前移动4步。接下来两个指针以相同的速度在链表上向前移动，直到它们相遇。它们相遇的结点正好是环的入口结点。

现在，关键问题在于怎么知道环中有几个结点呢？

可以使用快慢指针，一个每次走一步，一个每次走两步。如果两个指针相遇，表明链表中存在环，并且两个指针相遇的结点一定在环中。

随后，我们就从相遇的这个环中结点出发，一边继续向前移动一边计数，当再次回到这个结点时，就可以得到环中结点数目了。

代码实现(c )

/*
struct listnode {
    int val;
    struct listnode *next;
    listnode(int x) :
        val(x), next(null) {
    }
};
*/
class solution {
public:
    listnode* entrynodeofloop(listnode* phead)
    {
        if(phead == null){
            return null;
        }
        listnode* meetingnode = meetingnode(phead);
        if(meetingnode == null){
            return null;
        }
        // 回环链表结点个数
        int nodesloop = 1;
        // 找到环中结点个数
        listnode* pnode1 = meetingnode;
        while(pnode1->next != meetingnode){
            pnode1 = pnode1->next;
            nodesloop  ;
        }
        pnode1 = phead;
        // 第一个指针向前移动nodesloop步
        for(int i = 0; i < nodesloop; i  ){
            pnode1 = pnode1->next;
        }
        // 两个指针同时移动，找到环入口
        listnode* pnode2 = phead;
        while(pnode1 != pnode2){
            pnode1 = pnode1->next;
            pnode2 = pnode2->next;
        }
        return pnode1;
    }
private:
    // 使用快慢指针，找到任意的一个环中结点
    listnode* meetingnode(listnode* phead){
        listnode* pslow = phead->next;
        if(pslow == null){
            return null;
        }
        listnode* pfast = pslow->next;
        while(pfast != null && pslow != null){
            if(pfast == pslow){
                return pfast;
            }
            pslow = pslow->next;
            pfast = pfast->next;
            if(pfast != null){
                pfast = pfast->next;
            }
        }
        return null;
    }
};

代码实现(python)

# -*- coding:utf-8 -*-
# class listnode:
#     def __init__(self, x):
#         self.val = x
#         self.next = none
class solution:
    def entrynodeofloop(self, phead):
        # write code here
        if phead == none:
            return none
        meetingnode = self.meetingnode(phead)
        if meetingnode == none:
            return none
        nodeslop = 1
        node1 = meetingnode
        while node1.next != meetingnode:
            node1 = node1.next
            nodeslop  = 1
        node1 = phead
        for _ in range(nodeslop):
            node1 = node1.next
        node2 = phead
        while node1 != node2:
            node1 = node1.next
            node2 = node2.next
        return node1
    def meetingnode(self, phead):
        slow = phead.next
        if slow == none:
            return none
        fast = slow.next
        while fast != none and slow != none:
            if slow == fast:
                return fast
            slow = slow.next
            fast = fast.next
            if fast != none:
                fast = fast.next
        return none