[Java] LeetCode 2095: Delete the Middle Node of a Linked List

[문제 바로 가기] - Delete the Middle Node of a Linked List

문제 해석

head라는 Linked List가 주어질 때, 중간 노드를 삭제하고 수정된 Linked List head를 리턴하는 문제. 이때 중간 노드는 Linked List의 길이가 n일 때 [n / 2]번째 노드를 말한다.

---

💡 아이디어

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

문제에 주석으로 ListNode가 어떻게 구현되어 있는지 보여준다. 이걸 참고해서 풀면 된다.

처음에는 ListNode의 길이를 센 후 중간 노드까지 이동한 후 중간 노드를 없애는 방법을 사용했다. 이때 주의할 점은 (n이 1일 경우 = 노드가 한개일 경우)에는 null을 리턴해야 한다.

총 길이인 len을 구한 뒤, 중간 노드의 길이인 mid 직전까지 이동한 후 cur.next = cur.next.next를 통해 중간 노드를 삭제해준다.

★ 이때 cur은 head가 가리키는 연결 리스트의 내부 노드를 참조하고 있기 때문에, 즉 같은 연결 리스트 구조 내의 노드를 공유하고 있으므로 cur을 통해 리스트를 수정하면 head에도 반영된다. 따라서 head를 리턴해도 수정된 연결 리스트가 그대로 유지된다.

첫번째 풀이 : 길이 탐색 후 삭제

class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (head.next == null) return null;

        int len = 0;
        ListNode temp = head;

        while (temp != null) {
            len++;
            temp = temp.next;
        }

        int mid = len / 2;
        ListNode cur = head;

        for (int i = 0; i < mid - 1; i++) {
            cur = cur.next;
        }

        cur.next = cur.next.next;

        return head;
    }
}

다른 풀이는 없을까 찾아보다가 투 포인터를 사용할 수 있음을 알게 되었다.

빠른 포인터(fast), 느린 포인터(slow)를 각각 두고 fast는 2칸씩, slow는 1칸씩 이동하면 slow는 중간 노드에 도착하게 된다.

예시 1번을 보면 다음과 같다.

	1회	2회	3회	4회
slow	3	4	7 (중간 노드)
fast	4	1	6	종료 (fast.next == null)

이때 prev는 중간 노드의 바로 앞이므로 prev.next = slow.next를 해주면 중간 노드를 삭제하게 된다.

두번째 풀이 : 투 포인터

class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (head.next == null) return null;

        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;

        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        prev.next = slow.next;

        return head;
    }
}