[LeetCode] 876. Middle of the Linked List - 문제풀이

Description

주어진 LinkedList의 가운데 노드를 찾아서 반환하는 문제입니다. 노드의 수가 짝수개일때는 가운데 노드중 오른쪽 노드를 반환해 주시면 됩니다. 

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

public class ListNode {
    public int val;
    public ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Solution 1. List 길이 체크

public ListNode middleNode(ListNode head) {

    // 1. 공간복잡도 O(1) 시간복잡도 O(N)+O(N/2)
    int nodeCnt = 0;
    ListNode node = head;
    while(node != null) {
        nodeCnt++;
        node = node.next;
    }
    int mid = nodeCnt/2+1;  
    node = head;
    for (int i = 1; i < mid; i++) {
        node = node.next;
    }
    return node;
}

순회하며 LinkedList의 Length를 구해서 가운데 인덱스의 Node를 다시 순회하며 찾아 리턴해 줍니다.

추가적인 공간없이 처리할 수 있어 공간복잡도는 O(N)이지만 시간복잡도가 길이를 확인 하기 위한 O(N)과 다시 중간 인덱스 노드를 찾기 위한 O(N/2)이 추가되나 직관적인 로직으로 가독성이 좋습니다.

Solution 2. List 길이 체크 + 배열이용

public ListNode middleNode(ListNode head) {

//2. 배열을 이용 공간복잡도 O(N), 시간복잡도 O(N)
    ListNode[] a = new ListNode[100]; // 최대 100
    ListNode node = head;
    int i = 0; //마지막 index+1 = length
    while(node != null) {
        a[i++] = node;
        node = node.next;
    }
    return a[i/2];
}

첫번째 문제 풀이와 비슷하지만 추가적인 공간을 이용해 시간복잡도를 줄였습니다.

LinkedList의 길이를 체크하면서 순회할때 각각의 인덱스에 맞게 배열에 넣어주고 중간 위치의 인덱스를 찾아 배열에서 바로 꺼내서 반환합니다. 시간복잡도, 공간복잡도 모두 O(N).

Solution 3. Fast and Slow Pointer

public ListNode middleNode(ListNode head) {

    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

하나씩 순회하는 slow 포인터와 두칸씩 순회하는 fast를 만들어줌. fast 포인터가 마지막에 있을때 절반씩 순회하는 slow포인트의 위치를 반환해 주면 됩니다. 시간복잡도 O(N), 공간복잡도 O(1)

Ploblem Source

Middle of the Linked List - LeetCode