[JAVA] 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:

• The number of nodes in the list is in the range [1, 100].
• 1 <= Node.val <= 100

아이디어

- 연결 리스트의 중간 노드를 구하는 방식을 찾아야 함, 문제의 연결 리스트는 단방향 연결 리스트임

- 같은 방향으로 같은 거리만큼 이동하는 A와 B의 속력이 2배 차이 날 때, 더 빠른 B가 도착한 시점에서의 A의 위치는 중간지점일 것이다.

- 위와 같은 논리로 포인터 두개를 사용해 풀어보자

- 첫번째 포인터는 하나씩 이동한다.

- 두번째 포인터는 두개씩 이동한다.

- 포인터는 현재 노드가 가르키는 다음 노드가 null이거나 그 다음노드가 null인 경우 <- 이 이전까지 이동한다.

풀이

/**
 * 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 firstPointer = head;
        ListNode secondPointer = head;
        
        //secondPointer가 firstPointer보다 두배 빠른 속도로 이동.
        while(secondPointer != null && secondPointer.next != null){
            firstPointer = firstPointer.next;
            secondPointer = secondPointer.next.next;
        }
        
        return firstPointer;
    }
}