LeetCode 02: Linked List Cycle 2

문제링크: https://leetcode.com/problems/linked-list-cycle-ii/

Problem

주어진 linked list에서 cycle이 시작되는 노드를 찾는 문제이다. cycle이 있으면 cycle이 시작되는 노드를 return, cycle이 없으면 Null값을 return하면 된다.

• 여기서 cycle이 시작되는 노드는 linked list의 tail과 연결된 노드이다.

Solution

Linked List Cycle 1의 문제를 풀어보았다면 같은 접근 방식을 이용해 쉽게 문제를 풀 수 있다.

두 접근 방식을 동일하게 이용하여 문제를 풀어보았다.

1) 거쳐간 노드를 표시

• 거쳐간 노드의 value 값을 None으로 업데이트한다. 노드의 value값이 처음 다시 None인 위치에 도달하면 해당 노드가 cycle의 시작 노드이다.

rtype = None
current = head

while (current)
	if (current.value == None):
		rtype = current
		break
	else:
		current.value = None
		current = current.next

return rtype

2) current, fcurrent 값의 비교

• cycle의 유뮤를 찾는 문제에서 한 칸씩 이동하는 노드(current)와 두 칸씩 이동하는 노드(fcurrent)가 같아지는 지점이 존재하면 cycle이 존재한다고 하였다.

• current와 fcurrent가 같아지는 지점에서 cycle이 시작하는 지점까지의 거리와, head에서 cycle이 시작하는 지점까지의 거리가 항상 동일하다는 사실을 이용하자.
  간단한 증명은 다음과 같다.
  
  A: cycle의 시작 위치 (우리가 구하고자 하는 노드)
  B: current와 fcurrent가 만나는 지점
  a: Head에서 A노드까지의 거리
  b: A노드에서 B노드까지의 거리
  c: 한 cycle의 총 거리

• Head에서 시작한 current, fcurrent가 B노드에서 만날 때, fcurrent는 current에 비해 이동한 거리가 2배이다. 따라서 다음과 같은 식이 성립한다. (n은 fcurrent가 돈 cycle의 횟수)
  따라서, 해당 수식을 통해 A에서 Head까지의 거리와 B에서 A까지의 남은 거리가 동일하다는 것을 확인할 수 있다.

  2(a + b) = a + b + nc
  a + b = nc
  a = nc - b
  (a는 Head에서 A까지의 거리, nc-b는 B에서 A까지의 남은 거리)

• current와 fcurrent가 만나는 지점에서부터 새로 시작하는 노드를 형성해서 cycle이 시작하는 지점까지 이동하면 cycle의 시작점을 구할 수 있다.

current = head
fcurrent = head

while (fcurrent!=None and fcurrent.next!=None):
    current = current.next
    fcurrent = fcurrent.next.next

    if (fcurrent == current):
        current2 = head

        while (current != current2):
            current = current.next
            current2 = current2.next
        rtype = current
        break
        
return rtype