Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integerposwhich represents the position (0-indexed) in the linked list where tail connects to. Ifposis-1, then there is no cycle in the linked list.
주어진 연결리스트에서, 순환이 있는지 확인해라
주어진 연결리스트 안의 순환을 나타내기위해, tail 부분에서 연결된 포지션을 정수로 나타내는 것을 사용한다. 만약 포지션이 -1 이면, 연결리스트에 순환부가 없는 것이다. (pos 포지션은 페이크고, 그냥 bool 순환여부 확인하면됨)
조건으로, 시간복잡도 O(1) 로 풀어봐라
e.g.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Follow up:
Can you solve it usingO(1)(i.e. constant) memory?
Process
// Process //1. Input head node pointer
//2. Check if head is null or not
// 2.1. If not -> Iterate till node->next is not null
// 2.1.1. Check if it's pointing itself
// 2.1.1.1. If so -> it's cycle
// 2.1.2. Move to next node
// 2.1.3. Make previousBuff node point itself
//3. Return result cycle boolean
// 처리과정
//1. 헤드노드 포인터 입력받는다.
//2. 입력받은 포인터가 null 인지 확인해서
// 2.1. null이 아니면 -> 노드의 next 가 null 이 아닐때까지 반복한다.
// 2.1.1. 해당 순번 노드의 next 가 본인을 가리키는지 확인한다.
// 2.1.1.1. 맞다면 -> 사이클 존재한다.
// 2.1.2. 다음 노드로 넘어간다.
// 2.1.3. 이전의 노드 next 값을 본인을 가리키도록 바꿔놓는다.
//3. 사이클 유무 결과 반환한다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
class Solution {
public:
bool hasCycle(ListNode *head) {
bool result = false;
if (head != 0) {
if (head->next == head)
result = true;
while (head->next != 0 && !result) {
if (head->next == head) {
result = true;
}
else
{
ListNode *tempNode = head;
head = head->next;
tempNode->next = tempNode;
}
}
}
return result;
}
};
