[Leet Code] Two Pointers (투포인터): 876.Middle of the Linked List - Easy

문제 / 코드

드디어 linked list가 나왔다. 링크드리스트 자료구조 포스팅이랑 같이 올리려고 했는데 시간이 너무 늦어 다음 코드리뷰 포스팅이랑 같이 올려야겠다 (어차피 앞으로 링크드리스트 주구장창 나올 예정이기 때문에..)

 

 

Description

Return middle node of the linked list. If there are two middle nodes, return the second middle node.

 

How to solve

Simple way

1. Iterate the linked list from the first node to get the full length.
2. Iterate the linked list from the first node again, change the current head to its next node in each loop.
3. Stop the iteration when the count of the loop reaches round(length/2 + 0.1) = means middle when the full length is a positive number and the next integer of length/2 when the full length is a odd number.
4. Return the current node.

Two pointers

The key to solve this problem is to recall that x = 1/2y is equals 2x = y.

 

The answer we need to get is 1/2length(linkedlist). That means we can set one variable x and x will be the answer once 2x = length(linkedlist).

1. Iterate the linked list with two pointers, the point pointers points first nodes of the list at the first loop.
2. In each loop, one pointer moves 2 nodes, the other pointer moves one node.
3. When the faster pointer reaches the end of the linked list, stop the loop and return the node where the slower pointer is pointing.

 

Pseudo Code

Simple way

p, cnt = head, 0
while p.next:
    cnt+=1
    p = p.next
for _ in round(cnt/2 + 0.1):
    head = head.next
return head

Two pointers

fast, slow = head

while fast, fast.next:
    fast = fast.next.next
    slow = slow.next
return slow

(+) why loop condition needs to be fast and fast.next?

- If we set fast.next as while condition:

The faster pointer moves two nodes. That means when it reaches a node before last node, fast.next.next is None so fast is be replaced to None. Therefore, Nonetype error will be raised at while code in the next loop.

 

- If we set fast as while condition:

Same as above, while condition will pass but Nonetype error will raised at fast = fast.next.next code.

 

So we need to set while condition to fast and fast.next to prevent Nonetype error.