[ Top Interview 150 ] 141. Linked List Cycle

문제

141. Linked List Cycle

  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.

• Input : ListNode의 head
  • 각 node는 Singly-Linked List 형식으로 이루어져 있음
  • 각 상황에 따라 순환이 존재할 수 있다.
• Output : 해당 Singly-Linked List에 순환 유무

알고리즘 1차 전략 (Set 이용)

• 가장 먼저 떠오른 자료구조 Set 를 이용한다.

• 해결 전략

  • head부터 Set에 넣는다.
  • 다음 node로 건너가는 것을 반복한다.
    • node가 null일 경우 false를 반환
    • node가 Set에 있을 경우 true를 반환
    • 위 두 경우가 아닌 경우 해당 node를 Set에 넣는다.

1차 답안

• Time complexity : O(n)
• Space complexity: O(n)

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> nodes = new HashSet<>();

        ListNode currentNode = head;
        while (currentNode != null) {
            if (nodes.contains(currentNode)) {
                return true;
            }
            nodes.add(currentNode);
            currentNode = currentNode.next;
        }

        return false;
    }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

알고리즘 2차 전략 (Floyd's Cycle Detection Algorithm 이용)

• Floyd's Cycle Detection Algorithm

  • 한 칸씩 이동하는 포인터, 두 칸씩 이동하는 포인터를 만든다.
  • 이 둘이 이동하면서 서로 같은 객체를 가리키게 될 경우, 해당 Linked List는 순환한다.
  • 반면 null을 만나게 될 경우, 해당 Linked List는 순환하지 않는다.

• 해결 전략

  • moving1, moving2에 각각 head, head.next를 가리킨다.
  • moving1, moving2가 각각 한 개, 두 개 node씩 이동하면 아래 과정을 반복한다.
    • moving2가 null을 가리키게 될 경우, false를 반환한다.
    • 이 둘이 이동하면서 서로 같은 객체를 가리키게 될 경우, true를 반환한다.

2차 답안

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }

        ListNode moving1 = head;
        ListNode moving2 = head.next;

        while (moving2 != null) {
            if (moving1 == moving2) {
                return true;
            }

            moving1 = moving1.next;
            moving2 = doublyNextNode(moving2);
        }
        return false;
    }

    private ListNode doublyNextNode(ListNode node) {
        ListNode nextNode = node.next;
        if (nextNode == null) {
            return null;
        }
        return nextNode.next;
    }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

좀 더 간단한 답안

• Floyd's Cycle Detection Algorithm 이용
• 위의 코드보다 좀더 간결하게 작성함

public class Solution {
    public boolean hasCycle(ListNode head) {

        ListNode s = head;
        ListNode f = head;
        while(f != null && f.next != null){
            s = s.next;
            f = f.next.next;
            if(s == f){
                return true;
            }
        }
        return false;
    }
}