[Linked List] Linked List Cycle

141. Linked List Cycle

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

본 문제는 해결하지 못했습니다.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
  if(!head)
    return false;  
  
  while(head){
    if(!head.next)
      return false;
    
    if(findSameVal(head))
      return true;    
    
    head = head.next;
  }  
};

var findSameVal = function(head){
  let cur = head;
  
  while(cur){
    if(head === cur)
      return true;
    
    cur = cur.next;
  }
  
  return false;
}

연결리스트를 순회할 때, 현재 노드와 같은 요소가 나머지 노드들에 있는지 검사하는 로직입니다. 하지만, 순회하는 요소를 찾지 않고, 중복된 요소만 찾기 때문에 타당하지 않습니다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

이전에 필자가 수행한 해답이 있어서 참고하였습니다.

/**
 * Runtime	: 68 ms
 * Memory	: 45.16 MB
 */
var hasCycle = function(head) {
  if(!head)
    return false;  
  
  let slow = head;
  let fast = head;
  
  while(fast){
    if(!fast.next)
      return false;
    
    else{
      fast = fast.next.next;
      slow = slow.next;
    }
    
    if(fast === slow)
      return true;
  }
  return false;
};

Runner 방법은 연결리스트를 순회할 때 2개의 포인터를 사용합니다. 빠른 포인터(fast)는 2칸씩, 느린 포인터(slow)는 1칸씩 이동하여 빠른 포인터가 연결리스트의 끝에 도달 했을 때, 느린 포인터는 연결리스트의 중간에 도달함을 이용합니다.

Example 1에서

Input:  head = [3,2,0,-4], pos  =  1

fast는 3 → 0 → 2 → -4, slow는 3 → 2 → 0 → -4 → 2 → 0 → -4 순으로 탐색합니다.

풀이의 핵심은 반복의 시작인 2를 보는 것이 아니라 끝인 -4가 동일해질 때입니다.