(Easy - Fast & Slow Pointers) Leetcode - 876. Middle of the Linked List

이 문제는 Linked-List에서 중간에 있는 노드를 찾아 반환하는 문제입니다.

만약 배열이면 배열의 크기를 찾아 반으로 나눠 쉽게 중간값을 찾을 수 있습니다.

하지만 Linked-List는 index가 아닌 포인터로 연결되어 있기에 포인터를 사용해야 합니다.

 

이때 Slow and Fast Pointer라는 걸 사용할 수 있습니다. 런너 기법이라고도 불립니다.

Slow는 한 번에 한 칸씩 이동하는 포인터이고 Fast는 한 번에 두 칸씩 이동하는 포인터입니다.

Slow 포인터가 한 칸 이동할 때 Fast 포인터는 두 칸 이동하므로 Fast 포인터가 Linked-List의 맨 마지막 노드

혹은 nullptr에 도달하면 Slow 포인터는 Linked-List의 중간에 도달하게 됩니다.

 

While Loop를 통해 Slow와 Fast 포인터를 이동시킬 때 fast와 fast->next가 nullptr이 아닌지 확인해줍니다.

그리고 loop가 끝났을 때 Fast 포인터가 만약 nullptr이 아니라면 Linked-List의 노드의 개수가 홀수라는 의미입니다.

노드의 개수가 짝수라면 두 개의 중간 노드들 중 더 멀리 있는, 오른쪽 노드가 Slow 포인터의 노드가 됩니다.

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if (!head) return nullptr;
        ListNode* slow = head;
        ListNode* fast = head;

        // fast node moves 2 times faster than slow, so when fast node reaches to the end,
        // slow node reaches to the middle
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // if Linked-List has odd number of nodes, fast node is not null when while loop is ended

        return slow;
    }
};