LeetCode Linked List Cycle

1. 题目

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

Follow up:

Can you solve it without using extra space?

2.解决方案

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head){
		return false;
	}

	ListNode* slowPoint = head;
	ListNode* fastPoint = head;

	while(slowPoint->next){
		//slow point move one step
		slowPoint = slowPoint->next;
		//fast point move two step
		if(fastPoint->next){
			fastPoint = fastPoint->next;
		}else{
			return false;
		}
		if(fastPoint->next){
			fastPoint = fastPoint->next;
		}else{
			return false;
		}
		if(slowPoint->val == fastPoint->val){
			return true;
		}
	}
	return false;
    }
};

思路：用快慢指针来走，如果有环的话，一定会遇到一起。

http://www.waitingfy.com/archives/1588

数据结构 & 算法 | RSS 2.0 |