[LeetCode/Kotlin]Easy - 141. Linked List Cycle

Linked List Cycle - LeetCode

문제

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, 104].
• 105 <= Node.val <= 105
• pos is 1 or a valid index in the linked-list.

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

풀이

나의 풀이법

풀이 접근 과정

나는 set을 사용해서 중복으로 입력된 값이 있으면 순환하는 리스트라고 생각했다.

하지만 그냥 중복되는 숫자가 있는 걸로…

결국 tail 값을 찾아내야 하는데 ListNode 클래스에서 tail 값을 찾아내는 법을 몰랐다.

그래서 결국 해결하지 못하고 풀이법을 찾아봤다.

다른 풀이법

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */

class Solution {
    fun hasCycle(head: ListNode?): Boolean {
        var slow = head
        var fast = head

        while (fast != null && fast.next != null) {
            slow = slow?.next
            fast = fast.next?.next

            if (slow == fast) {
                return true
            }
        }

        return false
    }
}

위 코드는 투 포인터(Two Pointer) 방식을 사용하여 순환 여부를 판별합니다. slow 포인터는 한 번에 한 노드씩 이동하고, fast 포인터는 한 번에 두 노드씩 이동합니다. 만약 순환 구조가 없다면, fast 포인터가 연결 리스트의 끝에 도달할 것입니다. 그러나 순환 구조가 있다면, fast 포인터와 slow 포인터가 언젠가는 만날 것입니다.

 

 

---

Comment

생각보다 복잡하고 어려웠다.

이게 Easy라고..?

ListNode 클래스가 주어지는데 그걸 사용해서인지 더 난해하고 어렵게 느껴졌다.

프로그래머스와 비교하여 LeetCode에서 느끼는 벽은 이런 부분인 것 같다…

그리고 pos는 대체 왜 쓰는거지? 매개변수로 받지도 않는다 ㅋㅋ