876. Middle of The Linked List | 연결리스트의 중간

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

 

이 문제는 연결리스트에서 중간값을 찾아 중간부터 출력하는 문제다.

 

예시1.

Input : head = [1,2,3,4,5]

Output : [3,4,5]

 

중간값이 3이기 때문에 [3,4,5]가 출력되어야 한다.

 

예시2.

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]

 

중간값이 4이기 때문에 [4,5,6]이 출력되어야 한다.

 

이 문제에서는 주석으로 ListNode의 구조가 주어지는데 이를 보고 출력을 결정하면 된다.

 

이 문제를 해결하는 핵심은 중간 노드를 어떻게 찾느냐인데,

두개의 노드를 만들어서 계산하면 된다.

fnode : 중간 지점을 반환할 노드

lnode : 2개씩 이동하며 연결 리스트를 2분할 하는 노드

 

즉, lnode가 2개씩 노드를 건너뛰어서 연결 리스트를 반으로 줄이고, fnode는 1개씩 이동하여 중간 지점을 정한다.

아래는 그것을 구현한 코드이다.

/**
 * 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 fnode = head; // 시작 노드
        ListNode lnode = head; // 마지막 노드
		
        // 무한 반복
        while(true){
            try {
                lnode = lnode.next.next; // 마지막 노드는 2개씩 움직임
            }
            catch (NullPointerException e){ // 만약에 끝까지 도달했다면 탈출
                break;
            }
            fnode = fnode.next; // 시작 노드를 옮김
        }

        return fnode;
    }
}

 

여기서 아쉬운점은 내가 lnode가 끝에 다다랐을때 null을 반환하는것을 어떻게 처리할지 고민하다가

그냥 try-catch문으로 체크했는데 일단 작동은 잘 된다...;;