Today I Learned

오늘도 안드 공부하면서 코테 공부!

141. Linked List Cycle

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

문제

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.

풀이 과정 & Java 코드

• 처음엔 유니온 파인드 같은걸 써야하나? 하고 생각했는데 문제에서 원하는건 좀 더 간단한 해답으로 보여서 다른 방법으로 생각해보았다.

1. map

   public boolean hasCycle(ListNode head) {
      if (head==null) return false;
      Map<ListNode, Integer> map = new HashMap<>();
      map.put(head, 1);
      ListNode node = head;
      while (true){
         node = node.next;
         if (node == null) return false;
         if (map.containsKey(node)) return true;
         else map.put(node, 1);
      }
   }

• 먼저 map을 써서 풀어보았다. map에다가 key로 node를 넣고, value에다가 map에 들어간 횟수를 체크하는 식으로 구현했다.

• while문을 계속 돌면서 다음 노드로 이동하고, 해당 노드를 map에 키가 있는지 확인해서 있으면 기존에 지나갔던 노드이니 cycle이 형성되었으므로 true를 반환하고, 끝까지가서 null이 나오면 false가 되는 구조로 만들었다.

• 구현을 다하고 보니 굳이 map일 필요는 없는게 value가 의미 없어서 HashSet으로 해도 될 것 같다.

• 나름 간단하게 구현했지만 더 좋은 답안이 있어보였다.

2. Two-Pointer

    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode oneStep = head;
        ListNode twoStep = oneStep.next.next;

        while (twoStep != null && twoStep.next != null) {
            if (twoStep == oneStep) return true;

            twoStep = twoStep.next.next;
            oneStep = oneStep.next;
        }
        return false;
    }

• 투포인터를 이용해서 사이클을 찾는 방법이다.

• 포인터로 활용할 변수 2개를 만들어 하나는 head에서 시작해 next 한단계씩 움직이고, 다른 하나는 head의 다음다음에서 시작해 next 2단계씩 움직인다.

• 만약 사이클이 형성되어있다면 두 변수는 끝까지 null이 나오지 않고, 결국엔 서로 만나게 될 것이다.