141. Linked List Cycle

 

https://leetcode.com/problems/linked-list-cycle/

Linked List Cycle - LeetCode

 

연결리스트에서 cycle이 존재하는지 판별하는 문제.

 

---

 

 

1. 문제 이해

 

=> Given head, the head of a linked list, determine if the linked list has a cycle in it. (문제의 요구사항. head노드가 주어지면, 연결리스트가 cycle이 있는지 판별하라.)

 

=> There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.(pos가 파라미터로 주어지지 않는다는 점에서 주의.)

 

=> Return true if there is a cycle in the linked list. Otherwise, return false.

 

제한사항

• The number of the nodes in the list is in the range [0, 104]. (제한사항 그냥 넘어갔다가 노드가 0개 일때 처리를 못해줘서 에러 떴음. 제한 사항 주의해서 보자.)
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

 

---

 

2. 문제 재정의

인풋과 아웃풋을 볼까??

 

Input: head = [3,2,0,-4], pos = 1

Output: true

 

Input: head = [1], pos = -1

Output: false 

 

음... 처음에 파라미터로 헤드 노드만 주어지고, 로직을 통해 연결리스트가 cycle이면 true, 그렇지 않다면 false를 반환하면 되는구만.

 

 

 

---

 

3. 계획 수립

그렇다면 어떻게 헤드노드만 통해 연결리스트가 cycle인지 아닌지 판별할 수 있을까?

 

일단 cycle이 존재하는지 아닌지는 연결리스트를 필수적으로 한 바퀴 돌아봐야 아니까 O(n) 이상이다.

 

첫 접근 : cycle이면 다시 돌아가게 될테니 current node ptr생성 후, while문 돌면서 cur = cur->next 로 이 노드가 헤드노드에 도달시 true를 반환하게 할까? => cycle이 형성되는 지점이 head라는 보장이 없어서 실패!

 

두번째 접근 : 그렇다면 투포인터로 두 개의 ptr(fast ptr, slow ptr)를 생성 후에 속도 차를 이용해서 cycle이 있는지 판별해 볼까?

 

 

 

---

 

 

4. 계획 검증 

fast ptr은 slow ptr보다 더 빠르게 이동하니 만약 cycle이 존재하면, 어느 구간에서든 fast ptr이 slow ptr을 따라잡을 수 있다.

만일 cycle이 존재하지 않는다면, fast ptr이든 slow ptr이든 끝인 nullptr에 도달하게 되므로 false를 반환하면 된다!

 

 

---

 

 

5. 프로그램 구현 

/**
 * 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) {
        ListNode *fast = head, *slow = head;
        if (head == nullptr)
            return false;
            
            
        while (slow->next != nullptr && fast->next != nullptr && fast->next->next != nullptr ) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
                return true;
        }
        return false;
    }
};

 

 

---

 

 

6. 피드백 & 복기

 

더 빠르게 할 수 있는 방법이 없을까?

fast는 slow보다 항상 빠르니, while문에서 slow->next != NULL을 생략해줘도 된다.

 

더 빠른 코드:

/**
 * 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) {
        ListNode *first = head;
        ListNode *second = head;
        while (first != nullptr && first->next != nullptr)
        {
            first = first->next->next;
            second = second->next;
            
            if (first == second)
                return true;
        }
        
        return false;
    }
};

 

이보다 더 빠른 코드가 존재하긴 한데,

/**
 * 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) {
        if(head==NULL || head->next==NULL) {
   return false;
}
ListNode*a=head;
ListNode*b=head->next;
while (a!=b) {
    if (b==NULL || b->next==NULL) {
      return false;
    }
    a=a->next;
    b=b->next->next;
}
return true;
    }
};

 

접근하는 방식에는 큰 차이가 없는 듯 하다.