[ LeetCode _ 141 & 142 ] Linked List Cycle 1,2

Problem 

 

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

Linked List Cycle - LeetCode

 

 

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

Linked List Cycle II - LeetCode

 

How to Solve ?

 

1) 

Linekd List가 연결된지 확인하는 방법 중 가장 대표적인 방법으로 Walker & Runner Method가 존재한다.

 

워커는 한번에 한칸을 이동하고, 러너는 한번에 두칸을 이동하게 되는데 이렇게 접근을 하게 될 때, Walker & Runner가 만날 수 있다면 사이클이 존재하는거라 판단 할 수 있다.

 

function solution(head) {
  let walker = head;
  let runner = head;

  while (runner && runner.next) {
    walker = walker.next;
    runner = runner.next.next;
    if (walker === runner) {
      return true;
    }
  }
  return false;
}

 

2)

 

이 문제도 Walker & Runner Method를 응용하여 풀 수 있다.

 

1) 사이클이 연결된지 확인 하기위해  Walker & Runner Method 사용

( : 만약 없으면 null )

 

2) 사이클을 있는걸 확인했으면, 둘 중 한명을 head로 보내어 다른 사람과 만날 때까지 한 걸음씩 이동시킨다.

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function solution(head) {
  if (!head || !head.next) return null;

  let walker = head,
    runner = head;

  while (runner && runner.next) {
    walker = walker.next;
    runner = runner.next.next;

    if (walker === runner) {
      break;
    }
  }

  if (walker !== runner) return null;

  walker = head;

  while (walker !== runner) {
    walker = walker.next;
    runner = runner.next;
  }

  return walker;
};