首页 > 代码库 > 判断链表是否有环

判断链表是否有环

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

关键点:1)判断链表是否有环。

2)一个小坑在判断root和root的next是否为空上。

3)可以看为追及问题。最关键的坑在判断快走(每次走2步的节点),走1步会不会已经走到头。。。


/**

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        stack<ListNode*>    stk;
        ListNode    *nodeA,*nodeB;
        if(NULL ==  head||NULL  ==  head->next)
        {
            return  false;
        }
        nodeA   =   head;
        nodeB   =   head;
        while(NULL!=(nodeB->next->next))
        {
            nodeA=nodeA->next;
            nodeB=nodeB->next->next;
            if(nodeA    ==  nodeB)
                return  true;
            if(NULL ==  nodeB->next)
                return  false;
        }
        return  false;
    }
};

判断链表是否有环