문제

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

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.

linked list가 주어졌습니다, cycle이 있는 지 확인하십시오.

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

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)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

풀이

walker와 runner 방식으로 문제를 해결해 보겠습니다. 개념은 walker가 한 칸 갈 때 runner는 두 칸을 가기 때문에, runner가 끝에 닿으면 walker는 중간지점에 도달한다는 내용입니다. 자세한 내용은 leetcode876를 참고 부탁드리겠습니다.

여기서 walker와 runner 방식을 사용하는 이유는 따로 공간 복잡도를 만들지 않아도 되는 장점이 있기 때문입니다.

Answer :

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(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 false;
        else return true;
        
    }
}

위의 문제는 중간지점을 찾는 개념은 아니지만, 핵심은 cycle이 있다면 언젠가는 walker와 runner가 만날 것이며, cycle이 없다면 runner는 먼저 null에 닿을 것이라는 점입니다.

runner가 먼저 한 칸을 갑니다 runner.next
runner가 null이 아니라면 한 칸 더 갑니다 runner.next
walker가 한 칸 갑니다 walker.next

그 결과 walker가 한번 갈 때는 runner는 두 칸을 가게 됩니다.
다음과 같은 순서로 while 반복문을 순환하다가 break되는 경우가 두 가지가 있습니다. 한 가지는 runner와 walker가 만났을 경우이며, 다른 한 가지는 runner가 null에 닿았을 때입니다.
그 결과를 비교해 true와 false를 return 합니다

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

유튜브 승지니어 해당영상

← Previous Post Next Post →

LeetCode#141

Linked List Cycle

문제

기본 지식

풀이