[LeetCode] 876. Middle of the Linked List, Easy

1. 문제

• 단일 연결 리스트 head가 주어질 때, 연결 리스트의 중간 노드를 반환하라.
• 만약, 중간 노드가 2개(전체 길이가 짝수인 경우) 2번 째 노드를 반환하라.

2. 해결

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function middleNode(head: ListNode | null): ListNode | null {
    let fastPoint = head;
    let slowPoint = head;

    while(fastPoint && fastPoint.next) { // fastPointer가 null이 아니고, 마지막 노드가 아니라면 반복
        fastPoint = fastPoint.next.next;
        slowPoint = slowPoint.next;
    }

    return slowPoint;
};

• 문제를 처음보고 떠오른 해결 방법은 전체 길이 / 2 +1 을 활용하는 방법이었다. 근데, 이렇게 하면 시간 복잡도가 O(n^2) 가 나올 거 같애서 다른 방법이 없나 고민해봤다.
• 배열을 이용해서 각 노드의 인덱스를 기록하는 방법을 응용해볼까 했지만, 이것도 뭔가 맘에 안들었다. 배열을 한 개 더 선언하는 거기도 하고..
• Floyd's Tortoise & Hare Algorithm 이라고 토끼 거북이 알고리즘? 이라는 게 있더라. 처음 보는 거기도 하고 학습 겸 사용해봤다.
• 원리는 2개의 포인터를 사용해서 한 개는 1칸씩 이동하고, 나머지 한 개는 2칸씩 이동하게한다. 2칸 씩 이동하는 포인터가 null이 되거나 다음 노드가 없으면 1칸 씩 이동하던 포인터가 가리키는 노드가 중간 노드가 된다.
• 5개의 노드가 있는 경우,

Slow Pointer	Fast Pointer
1	1
Fast Pointer가 있고	Fast Pointer 다음 노드가 있으니까
2	3
Fast Pointer가 있고	Fast Pointer 다음 노드가 있으니까
3	5
Fast Pointer가 있지만,	Fast Pointer 다음 노드가 없으므로 종료

• 6개의 노드가 있는 경우,

Slow Pointer	Fast Pointer
1	1
Fast Pointer가 있고	Fast Pointer 다음 노드가 있으니까
2	3
Fast Pointer가 있고	Fast Pointer 다음 노드가 있으니까
3	5
Fast Pointer가 있고	Fast Pointer 다음 노드가 있으니까
4	null
Fast Pointer가 없으므로 종료