LeetCode 876(Middle of the Linked List, java)

0. 문제

https://leetcode.com/problems/middle-of-the-linked-list/

Middle of the Linked List - LeetCode

 

 

1. 문제 설명

- 문제에서 연결 리스트(head)가 주어진다.

- 전체 연결 리스트의 중간에 위치한 노드를 반환하는 것이 문제의 핵심이다. 

- 만약 중간에 위치한 노드가 2개라면 두 번째 중간 노드를 반환한다.

 

 

2. 문제 해설

a) 첫 번째 접근

- 이 문제는 연결 리스트의 중간 노드를 구하는 방식을 찾는 것이 관건이다.

- 문제에서 주어진 연결 리스트는 단방향으로, 다음 노드만을 알 수 있다.

- 그렇다면 어떻게 중간 노드를 구할 수 있을까?

 

- 생각해보자.

- 10km의 마라톤을 달리는 선수 A와 B가 있다.

- 선수 B가 선수 A보다 2배 빠르게 달린다면, 선수 B는 선수 A보다 결승점에 2배 빠르게 도착할 것이다.

- 즉, 선수 B가 결승점에 도달했을 때 선수 A는 중간 지점에 위치할 것이다.

- 이 논리를 이용하면 된다. 

 

 

b) 두 번째 접근

- 그렇다면 두배 빠르게 이동하는 것을 어떻게 표현할 수 있을까? 

- 이를 위해서 two pointers 방법을 사용한다. 

- 첫 번째 pointer는 한 칸씩 이동하도록 설정한다. 

- 두 번째 pointer는 두 칸씩 이동하도록 설정한다.

- pointer의 이동 조건은 현재 두 번째 pointer가 가리키는 노드 또는 다음 노드가 null이 아닌 경우다. 

- 이러한 조건을 갖는 이유는 두 번째 노드가 이미 결승지점을 통과했거나, 결승지점에 위치했을 경우에 해당하기 때문이다.

 

- 다음 코드를 보면서 이해해보자.

 

 

3. 정답 코드

class Solution {
    public ListNode middleNode(ListNode head) {
        
        ListNode first = head;
        ListNode second = head;
        
        while(second != null && second.next != null) {
            first = first.next;
            second = second.next.next;
        }
        return first;
    }
}