[LeetCode] 141. Linked List Cycle / Swift

[문제 보기]

141. Linked List Cycle

 

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

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.

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

 

Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.

 

Constraints:

• The number of the nodes in the list is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked-list.

 

Follow up: Can you solve it using O(1) (i.e. constant) memory?

 

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

Linked List Cycle - LeetCode

 

---

단방향 연결리스트에서 사이클 여부를 확인하는 문제이다.

처음에 접근한 방법으로는 

한개씩 노드를 앞으로 이동할 때마다 배열에 넣고 저장하고, 다음으로 이동할 노드 (next)가 이미 방문했던 노드인지를 확인하는 방법으로 구현했다. 이미 방문한지 확인하는 방법으로는 단순히 배열을 순회하면서 확인하는 방법으로 찾았다.

문제 조건에서 노드의 갯수는 최대 10^5개라서 이 방법으로 구현하면 한 노드에 100억번 연산이 필요하는 방법이다.

그래서 이 방법으로 제출했을때 시간초과가 떠서 다른 방법을 찾아서 해결해야했다.

 

두번째 방법은 어떻게 이런생각을 할 수 있는지 대단하다고 느꼈다..

두번째 방법은 알고보니 Floyd's Cycle-Finding Algorithm이라는것이었다. 

해당 알고리즘 소개:

https://codingfreak.blogspot.com/2012/09/detecting-loop-in-singly-linked-list_22.html

 

두번째 방법의 아이디어는 2개의 포인터를 이용해서 해결하는 방법이다.

반복문 안에서 하나의 포인터(rear)는 한번에 한칸씩 움직이고, 다른 포인터(front)는 한번에 두칸씩 움직인다.

만약 사이클이 없는 경우라면 front는 마지막 노드의 next(nil)까지 무사히 도착해서 nil이 될 것이다.

그리고 rear는 2칸에 움직이는 front에 비해 1칸만 움직이므로 front보다 항상 뒤에 있으므로 어디까지 일단은 신경쓰지 않아도 된다.

 

만약 사이클이 있는 경우라면 사이클이 처음 발생하는 노드(p)를 front가 먼저 지나가고 front는 안에서 빙글빙글 돌 것이다.

그리고 마찬가지로 rear도 한칸씩 움직이면서 노드(p)를 지나쳐 갈 것이고 그 안에서 빙글빙글 돌 것이다.

여기서 중요한데, rear와 front는 각각 한번에 진행하는 차이가 1이므로 원형 큐에서 순회하는것 처럼 분명히 언젠가는 만난다는 것이다.

정확히는 rear가 노드p에 들어간 순간, 사이클 내부의 노드의 수 * front에서 출발하고 rear에 도착하는 방향으로의 거리 차 만큼 반복하면 분명 사이클이 없는 상황에서 만날리 없었던 front와 rear는 만나게 된다.

이 점을 이용해서 사이클이 있는지 판별하면 된다.

 

실제 작동하는 상황을 동영상으로 확인하면 아래와 같다. discuss에 보면 좋은 설명도 많고 동영상도 올린게 있다! ☺️

https://www.youtube.com/watch?v=KoVAJlSOpXw 

 

 

처음 작성한 코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */

class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        var arr = [(ListNode, ListNode?)]()
        var cur = head
        while cur != nil {
            if arr.contains(where: { $0.0 === cur?.next}) {
                return true
            }
            arr.append((cur!, cur?.next))
            cur = cur!.next
        }
        
        return false
    }
}

 

 

최종 제출한 코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */

class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
       
        var front = head?.next
        var rear = head
        
        while front != nil {
            if front === rear { return true }
            front = front?.next?.next
            rear = rear?.next
        }
        
        return false
    }
}