[ LinkedList ] 876. Middle of the Linked List (JAVA)

리트코드 JAVA로 876번 문제 풀이

 

1. 문제 내용

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.

=> head라는 이름의 링크드 리스트가 주어지고 그 리스트의 중간 노드를 반환하라.
만약 중간 노드가 2개라면 두 번째 노드를 반환하라.

=> 여기서 알 수 있는 것 : length가 홀수일 때와 짝수일 때를 구분해야 한다는 것!

 

Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: node 3이 중간 노드이다.

Example 2:

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: 중간 노드가 2개이기 때문에 두 번째 노드인 4를 반환!

Constraints:

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

 

 

이 문제에서 말하는 Node는 문제를 풀 때 정의해 준다.
정의는 다음과 같다.

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; }
}

node에는 값인 val, 다음 노드인 next로 이루어져 있으며 생성자는 두 가지가 정의되어 있다.

 

 

 

2. 풀이

class Solution {
    public ListNode middleNode(ListNode head) {
        List<ListNode> arr = new ArrayList();
        while(head != null){
            arr.add(head);
            head = head.next;
        }

        return arr.get(arr.size()/2);
    }
}

1. ListNode를 제네릭으로 설정하여 List를 생성한다.

2. while문을 통해 next node로 넘어가면서 node 하나하나 arrayList에 넣어준다.

3. arraylist의 size()는 int로 반환된다. 따라서 홀수일 경우 반올림 상태로 값이 반환된다.
또한 size()가 짝수일 경우 배열 index는 어차피 0부터 시작이기 때문에 절반 값이 중간 노드의 중간 값이 된다.
따라서 size() / 2 값이 해당 index가 된다.

 

해당 풀이의 Beats와 Memory 값은 다음과 같다.

• Beats 75.49%
• Memory 40MB

 

 

2-2. return 부분을 살짝 바꿔본 풀이

class Solution {
    public ListNode middleNode(ListNode head) {
        List<ListNode> arr = new ArrayList();
        while(head != null){
            arr.add(head);
            head = head.next;
        }

        int length = arr.size();
        return length%2 == 0 ? arr.get(length/2) : arr.get(Math.round(length/2));
    }
}

삼항 연산자를 사용하였고, 홀수의 경우는 Math class의 함수를 사용하여 제대로 반올림한 후에 배열의 값을 불러오게끔 하였다.

 

해당 풀이의 Beats와 Memory 값은 다음과 같다.

• Beats 99.99%
• Memory 39.9MB

 

근데 왠지... linkedList 문제여서 ArrayList를 쓰면 안 될 것 같은 느낌적인 느낌 느낌..

시간 날 때 다시 풀어봐야겠다 ㅎ