Get Middle in ListNode(ListNode에서 중간 값 찾기)

연결 리스트의 중간 노드를 찾기 위해 두 개의 포인터(느린 포인터와 빠른 포인터)를 사용합니다.

 

• 초기화: slow 포인터는 리스트의 시작 노드인 head로, fast 포인터는 리스트의 두 번째 노드인 head.next로 초기화합니다.
• 이동: slow 포인터는 한 번에 한 노드씩 앞으로 이동하고, fast 포인터는 한 번에 두 노드씩 앞으로 이동합니다.
• 종료 조건: fast 포인터가 리스트의 끝에 도달하거나 끝을 넘어가면 루프가 종료됩니다. 이 시점에서 slow 포인터는 리스트의 중간에 위치하게 됩니다.

private ListNode GetMiddle(ListNode head) {
    if (head == null) return head;

    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

 

예를 들어, 리스트가 다음과 같다고 가정해 보겠습니다: 1 -> 2 -> 3 -> 4 -> 5

• 초기화: slow는 1, fast는 2
• 첫 번째 반복: slow는 2, fast는 4
• 두 번째 반복: slow는 3, fast는 null

이 시점에서 루프가 종료되고 slow 포인터는 리스트의 중간 노드인 3을 가리킵니다.