leetcodeのLinked List Cycle

チェーンテーブルにリングがあるかどうか見てみましょう.注意:余分なスペースは使用できません.
Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space?
解決方法:
1,まず,余分なスペースが利用可能であれば,アクセスしたノードをvectorに格納し,次に重複があるか否かを判断し,重複がある場合はループがある.
2、2つのポインタを定義して、1つは速くて、毎回2歩歩いて、1つは遅くて、毎回1歩歩きます.もし彼らが出会ったら、チェーンテーブルにリングがあり、出会い点は必ずリングの中にあることを示します.
コードは次のとおりです.

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow_travel = head;
			ListNode* fast_travel = head;
			while(slow_travel){
				slow_travel = slow_travel->next;
				if(slow_travel == NULL){
					return false;
				}
				fast_travel = fast_travel->next;
				if(fast_travel == NULL){
					return false;
				}
				fast_travel = fast_travel->next;
				if(fast_travel == NULL){
					return false;
				}
				if((fast_travel->val == slow_travel->val) && (fast_travel->next->val == slow_travel->next->val)){
					return true;
				}
			}
			return false;
    }
};

leetcodeのLinked List CycleII
テーマ:
Given a linked list, return the node where the cycle begins. If there is no cycle, return null .
Follow up: Can you solve it without using extra space?
つまり、
チェーンテーブルを1つ与え、リングの開始点を探し出す.ループがない場合はNULLを返します
問題の構想:
まず、上記の第1題の方法を利用して、ループがあるかどうかを探し出す.ループがある場合、性質を利用する:新しいポインタを指定し、速いポインタと遅いポインタが出会った点を指し、それから1つのポインタを指定し、headポインタを指して出発し、2つの新しいポインタが同時に出発し、彼らが出会った点はループの開始点である.
コードは次のとおりです.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
		ListNode *detectCycle(ListNode *head){
			pair<ListNode*, bool> ifCycle = hasCycle(head);
			ListNode* slow_travel = NULL;
			ListNode* fast_travel = NULL;
			int step = 0;
			if(!ifCycle.second){
				return NULL;
			}
			else{	
				slow_travel = ifCycle.first;
				fast_travel = ifCycle.first;
				while(1){
					slow_travel = slow_travel->next;
					fast_travel = fast_travel->next;
					fast_travel = fast_travel->next;
					step++;
				    if((slow_travel->val == fast_travel->val) && (slow_travel->next->val == fast_travel->next->val)){
						break;
					}
				}
			}	
			fast_travel = head;
			slow_travel = head;
			while(step){
				fast_travel = fast_travel->next;
				step--;
			}
			while(true){
				if((fast_travel->val == slow_travel->val) && (fast_travel->next->val == slow_travel->next->val)){
					break;
				}
				fast_travel = fast_travel->next;
				slow_travel = slow_travel->next;
			}
			return slow_travel;
		}
	     pair<ListNode*, int> hasCycle(ListNode* head){
			ListNode* slow_travel = head;
			ListNode* fast_travel = head;
			pair<ListNode*, int> ifCycle;
			while(slow_travel){
				slow_travel = slow_travel->next;
				if(slow_travel == NULL){
					ifCycle.first = NULL;
					ifCycle.second = false;
					return ifCycle;
				}
				fast_travel = fast_travel->next;
				if(fast_travel == NULL){
					ifCycle.first = NULL;
					ifCycle.second = false;
					return ifCycle;
				}
				fast_travel = fast_travel->next;
				if(fast_travel == NULL){
					ifCycle.first = NULL;
					ifCycle.second = false;
					return ifCycle;
				}
				if((fast_travel->val == slow_travel->val) && (fast_travel->next->val == slow_travel->next->val)){
					ifCycle.first = fast_travel;
					ifCycle.second = true;
					return ifCycle;
				}
			}
			ifCycle.first = NULL;
			ifCycle.second = false;
			return ifCycle;
		}
};

追加:
第1題と第2題はコードを書き直した.それぞれ以下の通りである.
第一題:

struct ListNode{
	int val;
	ListNode* next;
	ListNode(int x) : val(x), next(NULL){}
};
class Solution{
	public:
		bool hasCycle(ListNode* head){
			if(head == NULL){
				return false;
			}
			ListNode* fast = head;
			ListNode* slow = head;
			while(slow){
				fast = fast->next;
				if(fast == NULL){
					return false;
				}
				fast = fast->next;
				if(fast == NULL){
					return false;
				}
				slow = slow->next;
				if(slow == NULL){
					return false;
				}
				if(fast == slow){
					return true;
				}
			}
		}
};

2番目の問題:

struct ListNode{
	int val;
	ListNode* next;
	ListNode(int x) : val(x), next(NULL){}
};
class Solution{
	public:
		ListNode* deterCycle(ListNode* head){
			pair<bool, ListNode*> ifCycle = LinkedListCycle(head);
			if(ifCycle.first){
				ListNode* current = head;
				ListNode* collision = ifCycle.second;
				while(true){
					current = current->next;
					collision = collision->next;
					if(current == collision){
						return current;
					}
				}
			}
			else{
				return NULL;
			}
		}
		pair<bool, ListNode*> LinkedListCycle(ListNode* head){
			pair<bool, ListNode*> result = make_pair(false, (ListNode*)NULL);
			if(head == NULL){
				return result;
			}
			ListNode* slow = head;
			ListNode* fast = head;
			while(slow){
				fast = fast->next;
				if(fast == NULL){
					return result;
				}
				fast = fast->next;
				if(fast == NULL){
					return result;
				}
				slow = slow->next;
				if(slow == NULL){
					return result;
				}
				if(fast == slow){
					result.first = true;
					result.second = slow;
					return result;
				}
			}
		}
};