LeetCode - 141.Linked List Cycle

[Must-do Easy Question] 시리즈

How to effectively use LeetCode to prepare for interviews!! - LeetCode Discuss

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

Linked List Cycle - LeetCode

---

문제

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.

 

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.

---

LinkedList가 Cycle을 가지고 있는지 판단하는 문제이다.

head 에서부터 List를 순환하다가 다음 노드가 이전노드를 발견하면 Cycle이 있는 경우이니 바로 true를 return 한다.

이전에 있는 노드를 발견하지 못하고 next가 null 일 경우 Cycle이 없는 경우니 false를 return 한다.

 

노드의 next가 이전에 있던 노드인지 아닌지는 구분하는게 핵심인 것 같다. 

마음 같아서는 ListNode의 class 에 isVisited라는 변수를 통해 처리하고 싶긴 하나 그럼 ListNode 들을 전부 새로 CustomNode로 새로 생성해야 되기 때문에 효율적이지 못한 방법같다.

 

아니면 ListNode를 순회하면서 ArrayList에 저장한 뒤 다음 ListNode의 val 이 ArrayList에 있는지를 판단해서 Cycle의 유무를 가리는 것도 좋을 것 같다.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    public boolean hasCycle(ListNode head) {
        ArrayList<ListNode> arraylist = new ArrayList();
        if (head == null){
            return false;
        }
        if (head.next == null){
            return false;
        }
        
        while(true){
            arraylist.add(head);
            head = head.next;
            
            for(int i  = 0 ; i < arraylist.size() ; i++){
                if (arraylist.get(i) == head){
                    return true;
                }
            }
            
            if (head.next == null){
                break;
            }
        }
        return false;
        
    }
}

 

통과했다

Success

 

Details 

Runtime: 78 ms, faster than 5.51% of Java online submissions for Linked List Cycle.

Memory Usage: 39.6 MB, less than 5.71% of Java online submissions for Linked List Cycle.

 

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

라는 follow up이 있다. 좀더 좋은 방법이 있는지 고민해보자...

 

Cycle을 확인 할 수 있는 방법은 어떤게 있을까....

 

힌트를 봤다...

 

2개의 포인터를 만들어 하나는 2칸씩 리스트를 이동하고 하나는 한칸씩 리스트를 이동하게 한다.

리스트를 순회하는건 2칸씩 이동하는  포인터의 한칸 뒤의 값과 두칸 뒤의 값이 null 일때 멈춘다.

 

1. 리스트가 Cycle을 가지고 있을 경우

- while문 안에서 계속 순회하기 때문에 언젠간 두 포인터가 만난다.

 

2. 리스트가 Cylce이 없는 경우

- 두칸씩 이동하는 포인터의 다음과 다음다음칸의 노드가 먼저 null 이 된다.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    public boolean hasCycle(ListNode head) {
        
        ListNode runner_1 = head;
        ListNode runner_2 = head;
        
        if (head == null){
            return false;
        }
        if (head.next == null){
            return false;
        }
        
        while(runner_2.next != null && runner_2.next.next != null){
            runner_1 = runner_1.next;
            runner_2 = runner_2.next.next;
            
            if(runner_1 == runner_2){
                return true;
            }            
        }
        return false;

    }
}