142. Linked List Cycle II

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

Linked List Cycle II - LeetCode

 

이전 연결 리스트 사이클 문제와 동일한데, 차이점은 사이클이 시작되는 지점을 리턴.

 

 

---

 

 

1. 문제 이해

=> Given a linked list, return the node where the cycle begins. If there is no cycle, return null. (사이클이 시작되는 지점을 리턴하는 것을 제외하고는, 이전 문제와 완전 동일하다.)

 

=> 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.

 

=> Notice that you should not modify the linked list.

 

 

 

---

 

2. 문제 재정의

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

Output: tail connects to node index 1

 

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

Output: no cycle

 

이전 문제와 동일한 조건하에, 아웃풋으로는 cycle이 시작되는 지점의 포인터를 리턴하면 되겠군. cycle이 없으면 nullptr을 리턴하고.

 

---

 

3. 계획 수립

사이클이 시작되는 지점이라니, 막상 와닫지는 않는다. 어떻게 구하지? 투포인터 접근도 힘들 것 같고.

해시맵이나 set을 사용해서, 현재 포인터를 set에 넣고 포인터가 사이클을 지나 다시 돌아왔을 시 그 지점을 반환하도록 해볼까?

 

 

---

 

4. 계획 검증 

cycle이 있을 시 -> 모든 요구사항 충족.

cycle이 없을 시 -> 요구사항 충족. 포인터가 next로 이동하다 NULL을 만나면, 바아로 nullptr 반환.

시간 복잡도 -> 연결리스트 한바퀴만 돌면 되니, O(n)만에 해결 가능.

공간 복잡도 -> set의 길이가 연결리스트만큼이므로, O(n). 

 

---

 

 

5. 프로그램 구현 

 

 

#include <set>

/**
 * 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) {
        set <ListNode *> s;
        
        while (head != nullptr) {
            if (s.find(head) != s.end())
                return head;
            s.insert(head);
            head = head->next;
        };
        
        return nullptr;
    }
};

---

 

 

6. 피드백 & 복기

 

투포인터를 이용한 접근방법. 공간 복잡도 O(1).

 

/**
 * 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) {
           if(head == NULL)return NULL;
            ListNode* slow = head;
            ListNode* fast = head;
             ListNode* start = NULL;
        while(fast != NULL && fast->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                start = head;
                while(start != slow){
                    start = start->next;
                    slow = slow->next;
                   }
                 break;
            }
        }
        return start;
        
    }
};

https://leetcode.com/problems/linked-list-cycle-ii/discuss/1276795/C%2B%2B-solution-faster-than-99-with-explanation => 해설인데, 이해중임. 어렵네.