[LeetCode] 876. Middle of the Linked List

문제의 개념 자체는 쉬워 보이지만, 연결 리스트를 다루는법이 아직도 익숙하지 않아 포스팅을 하려고 한다... 어쨌든!

 

문제는 이렇다.

 

입력값으로 head, 연결 리스트가 주어지고, 그 연결 리스트의 중간값을 반환하면 된다. 하지만 중간값이 2개라면, 2번째 중간 값을 반환하면 된다.

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = slow = head

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

 

• 'slow'와 'fast' 두개의 포인터를 초기화 한다. 둘 다 처음에는 리스트의 head를 가리킨다.
• while loop는 fast 포인터가 끝에 도달 할때까지 반복된다.
• fast가 리스트의 끝에 도달하면, slow는 중간에 위치하게 된다.

이 방법은 연결 리스트를 딱 한번만 순회하기 때문에 효율이 좋은 알고리즘이다. O(N)의 시간 복잡도를 가진다.