876. Middle of the Linked List

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

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 전체값을 찾는다.

2. 전체값을 통해 중간값을 찾는다.

3. 중간값에 해당하는 노드는 재귀를 통해 찾는다.

/**
 * 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 {
    private int size;
    public ListNode middleNode(ListNode head) {
        size = 0;
        findLastIndex(head, 0);
        ListNode middle = getMiddleNode(head, size / 2);
        return middle;
    }

    public void findLastIndex(ListNode node, int index) {
        if (node == null) {
            size = index;
            return;
        }
        findLastIndex(node.next, index + 1);
    }

    public ListNode getMiddleNode(ListNode node, int index) {
        if (index == 0) {
            return node;
        }

        return getMiddleNode(node.next, index - 1);
    }
}