[Linked List] Middle of the Linked List

 

Linked List 자료구조를 다루는 문제이다. 

 

Pointer 2개를 사용하는 테크닉을 사용하여 중간의 node를 리턴하는 방식이다.

 

slow pointer는 옆으로 한 칸만 가고, 

fast pointer는 딱 2배의 속도인 옆으로 두 칸을 간다.

 

만약 fast pointer가 linked list의 끝에 도달하거나 끝보다 더 뒤에 있는 식으로 도달한다면, slow pointer는 자동으로 중간에 위치할 것이다(속도가 딱 반이므로, fast가 끝에 도달하면 slow는 그 반절인 중간에 있을 것).

 

Linked list이므로 일단 두 pointer를 head로 initialize해주고, 

뒤의 node에 접근하고 싶은 경우 .next 를 써주면 된다. 

뒤의 뒤 node에 접근하고 싶은 경우 .next.next 이렇게 하면 되는 것 같다.

 

 

끝에 도달하는 fast pointer, 그리고 끝에 도달하는 fast pointer의 그 다음 것도 None이 되면 더이상 리스트를 돌면 안된다. 끝에 도달했기 때문이다. 그래서 while문 하에서 pointer들이 옆으로 돌아간다.