문제

Given a linked list, return the node where the cycle begins. If there is no cycle, return null

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

연결된 목록이 있으면 cycle이 시작되는 노드를 반환하십시오. cycle이 없으면 null을 반환

주어진 linked list에서 cycle를 나타 내기 위해, 꼬리가 연결되는 linked list에서 위치 (0 인덱스)를 나타내는 정수 pos를 사용합니다. pos가 -1이면 링크 된 목록에주기가 없습니다.

Note : Do not modify the linked list.

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.

기본 지식

Linked List :

링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

풀이

이번 문제는 leetcode141의 연장선이니 참고 부탁드립니다.

walker와 runner의 이동 경로를 추적해 보면 다음과 같습니다.

walker: 3

runner: 3 -> 2

walekr: 2

runner: 0 -> -4

walker: 0

runner: 2 -> 0

위의 그림을 바탕으로 설명해보도록 하겠습니다. 이해가 쉽도록 다음과 같이 변수의 개념을 이용하였습니다.

위의 그림에서 walker, runner 개념을 적용하면 0에서 만날 것입니다. 그리고 코드상 첫 노드로 가는 부분 start에서 3으로 가는 길이도 해당됩니다.

A: 시작 노드부터 cycle의 처음 노드까지 길이 (start - 3 - 2 => 2)

B: cycle 전체의 길이 ( 2 - 0 - -4 => 3)

X: cycle의 처음 노드부터 현재 노드(walker와 runner가 만난 노드)까지의 길이 (2 - 0 => 1)

walker: A + X runner: A + B + X

위의 그림에서는 cycle을 한 바퀴만 돌고 만나기 때문에 runner = A + B + X 가 되었지만, 정형화해서 표현하면 A + nB + X가 됩니다. n바퀴의 cycle(B)을 돌고 X만큼 가서 walker를 만나기 때문입니다.

또한 walker와 runner 개념상 2 X walker = runner입니다. 즉 2A + 2X = A + nB + X 이고, 정리하면 A + X = nB입니다

이 말을 해석하자면 X지점과 시작 노드부터 두 워커를 전진시키면 cycle의 처음 노드에서 만나게 된다는 것입니다.

왜냐하면 nB라는 뜻은 cycle(B)의 시작점을 뜻하고, A + X 에서 X는 이미 walker의 현재 위치이기 때문에 walker와 시작점에서 각각 한 칸씩 전진하면 만나는 지점이 nB, 즉 cycle의 시작점일 것이며 그것이 곧 nB = A + X 의 A부분일 것입니다.

아래에서 한번 더 설명하도록 하겠습니다.

Answer :

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode walker = head;
        ListNode runner = head;
        
        while(runner!=null){   		//(가)
            runner = runner.next;
            if(runner!=null){
                runner = runner.next;
                walker = walker.next;
                if(runner == walker) break;
            }else break;
        }
        if(runner==null) return null;

        ListNode check = head;		//(나)
        while(check!=walker){
            check = check.next;
            walker = walker.next;
        }
        return check;        
    }
}

(가)부분의 코드는 walker와 runner가 만나는 지점 즉 X지점에서 walker가 return 될 것이며, (나)부분이 위에서 말한 X지점과 시작 노드부터 두 워커를 전진시키면 cycle의 처음 노드에서 만나게 됨을 코드로 표현한 것입니다.

이번 문제는 해석이 중요하며 해석이 난해하다면 많이 어렵게 느껴지실 것입니다. 모르시는 부분이 있다면 언제든지 댓글이나 연락 주시면 답변해드리겠습니다. 감사합니다.

출처 : 제가 알고리즘 문제에 막 감을 익히고 있는 단계여서 유튜버 승지니어님의 코드를 인용하였습니다. 도움되는 영상이 많이 있으므로 많은 방문 부탁드리겠습니다.

유튜브 승지니어 해당영상