[LeetCode] 876. Middle of the Linked List (java)

✏️ 문제 

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

 

🤖 알고리즘

 

#링크드리스트  #투포인터

 

 

🤯 풀이 방법

 

submission detail

 

주어진 리스트의 전체 길이를 구하고 절반까지 도달할 때까지 next로 이동하는 방식으로 풀었다.

메모리 효율이 좋지 않아서 확인해보니 투포인터를 이용해서 복사해서 길이를 구할 필요 없이

인덱스만 이용해서 한 바퀴만 돌게 푸는 게 더 효율적인 방법인 듯!

 

 

👾 구현 코드 (자바)

class Solution {
    public ListNode middleNode(ListNode head) {
        int length = 1;
        int half;
        int cur = 0;
        ListNode h;
        h = head;
        
        // 리스트의 길이 구하기
        while (h.next != null) {
            h = h.next;
            length++;
        }

        half = length / 2;
        while (cur < half) {
                cur++;
                head = head.next;
            }
        return head;

    }
}

 

 

 

Middle of the Linked List - LeetCode