LeetCode 01: Linked List Cycle

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

Question

주어진 linked list에 cycle이 있는지 없는지 확인하는 문제이다. Cycle이 있으면 return True, 없으면 return False를 하면 된다.

Basic Concept

• Class Linked List
  : 각각의 Node에는 두 개의 필드 저장

class ListNode(object):
    def __init__(self, x):
        self.val = x 
        self.next = None

Data: 각 노드에 저장된 value 값
Next: 해당 노드에 연결된 다음 노드

• LinkedList vs List (Time Complexity)
  • Insertion/Delete (at beginning, end of list)
    • Linked List: O(1)
    • List: O(n)
  • Lookup
    • Linked List: O(n)
    • List: O(1) (인덱스로 접근 가능)

Solution

1) 거쳐간 노드를 표시

• 이미 지나간 노드의 value값을 None으로 바꿔줌으로써 거쳐간 노드의 flag를 표시
• while (current)
  • value == None이면 (이미 거쳐간 노드라는 뜻 → cycle 존재)
    • return true
  • value ≠ None이면
    • value = None 저장
    • current = current.next (다음 노드로 옮김)

rtype = False

current = head
while (current):
	if current.val == None:
		rtype = True
			break
	else:   
		current.val = None
		current = current.next

2) current, fcurrent 값의 비교

• 한칸씩 건너가는 노드와 두칸씩 건너가는 노드를 비교
• 두개의 노드가 같게되는 지점이 존재하면 → cycle 존재
  • 건너뛰어가는 칸 수의차이가 한 칸이므로 만약 cycle이 있다면, 두 노드가 같게 되는 지점 무조건 존재
• while 조건문
  • fcurrent와 fcurrent.next 값이 있는 동안 순회
    : fcurrent, fcurrent.next 값이 모두 존재해야 다음 loop에서 fcurrent.next.next 계산 가능
  • fcurrent 존재 → current 노드는 당연히 존재

rtype = False
current = head
fcurrent = head

while (fcurrent and fcurrent.next):
    current = current.next
    fcurrent = fcurrent.next.next
    if (current == fcurrent):
        rtype = True
        break