[링크드 리스트 (Linked List)] LC #876 Middle of the Linked List

문제 설명

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints:


문제 링크: https://leetcode.com/problems/middle-of-the-linked-list/

1. 문제의 핵심: Two Pointers (느린/빠른 포인터)

링크드 리스트 문제에서 자주 사용되는 'Two Pointers' 기법, 그 중에서도 '느린 포인터와 빠른 포인터' (Slow and Fast Pointers)를 활용하는 대표적인 문제입니다. 마치 토끼와 거북이의 경주처럼, 두 포인터의 속도 차이를 이용해 원하는 지점을 효율적으로 찾을 수 있습니다.

핵심 아이디어: 한 포인터(fast)는 두 칸씩, 다른 포인터(slow)는 한 칸씩 이동시킨다. 빠른 포인터가 리스트의 끝에 도달했을 때, 느린 포인터는 정확히 중간 지점에 위치하게 된다.

2. 해결 전략

  1. slow와 fast 두 개의 포인터를 모두 리스트의 시작점(head)에서 초기화합니다.
  2. fast 포인터와 그 다음 노드(fast.next)가 `null`이 아닐 때까지 반복문을 실행합니다. 이 조건은 리스트의 끝에 도달했는지, 그리고 fast가 두 칸을 안전하게 이동할 수 있는지 확인합니다.
  3. 반복문 안에서 slow는 한 칸 (slow = slow.next), fast는 두 칸 (fast = fast.next.next) 이동합니다.
  4. 반복문이 종료되면, slow 포인터가 가리키는 노드가 중간 노드가 됩니다. 이 노드를 반환합니다.

3. Java 코드 구현

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}

💡 코드 세부 포인트