[Python] LeetCode - Middle of the Linked List

Problem

Solving Process

 

내가 푼 방법

1. head를 돌며 head 의 전체 length를 구해준다

2. head_length // 2 하여 중간 인덱스 값을 구한다.

3. head를 돌며 중간 인덱스 값 부터 return 한다.

 

하지만 ....

다른 풀이를 보니 더 천재적인 방법이 있었다.

투 포인터를 사용하여

P2와 P2.next 가 존재하는 동안 루프를 돌며

P1은 한칸씩 나아가고 (P1.next)

P2은 두칸씩 나아간다 (P2.next.next)

 

그렇게 해서 P2 혹은 P2.next가 None이 될 때 까지 나아가면

P1의 값은 middle값이 된다. (전체의 절반이 middle값이므로)

 

보면서 정말 감탄했다 ㅋㅋㅋㅋㅋㅋ 대단한ㅅ ㅏ람들이야 ... ( •̀ ω •́ )✧

 

Solution

내가 푼 방식

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = head
        idx = head_length = 0
        while curr:
            head_length += 1
            curr = curr.next
        mid = head_length // 2
        while head:
            if mid == idx:
                break
            head = head.next
            idx += 1
        
        return head

천재들이 푼 방식

# Time Complexity :  O(n)
# Space Complexity : O(1)
class Solution(object):
    def middleNode(self, head):
        # We need two pointers, one is head with one step each iteration, and the other is tmp with two steps each iteration.
        temp = head
        while temp and temp.next:
            # In each iteration, we move head one node forward and we move temp two nodes forward...
            head = head.next
            temp = temp.next.next
        # When temp reaches the last node, head will be exactly at the middle point...
        return head