LeetCode 19(Remove Nth Node From End of List, java)

0. 문제

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Remove Nth Node From End of List - LeetCode

 

 

1. 문제 설명

- 문제에서 연결 리스트(head)와 정수(n)가 주어진다.

- 연결 리스트를 탐색하여 뒤에서부터 n번째에 위치한 노드를 삭제하는 것이 문제의 핵심이다. 

 

 

2. 문제 해설

a) 첫 번째 접근

- 가장 먼저 떠오르는 방법은 Brute Force를 사용한 two path 방식이다.

- two path는 말 그대로 2번 탐색하는 방식을 말한다. 

 

- 첫 번째는 while문을 이용하여 연결 리스트의 길이를 구한다.

- 그리고 (전체 길이 - n)을 계산하여 m 번째 노드를 삭제해야 하는지 찾는다.

- 두 번째는 for문을 통해 m 번째 노드를 삭제한다.

 

- 그러나 Brute Force 방식은 효율적인 해결방법이 아니다.

- 연결 리스트 전체를 2번 탐색하기 때문이다. 

- 더불어, 문제의 Follow up을 확인해보면 two path가 아닌 one path로 해결할 수 있는지를 물어본다.

 

- 그렇다면 한 번에 탐색하여 찾아낼 수 있는 방법은 무엇일까? 

 

 

b) 두 번째 접근

- 연결 리스트에서 one path 방식으로  two pointers 방식이 있다.

- 이 문제에서는 two pointers 방식 중 하나인 slow & fast pointers 방식을 사용할 예정이다.

 

- 우선 slow와 fast라는 이름의 pointer를 생성한다.

- slow와 fast pointer는 dummy 노드로부터 시작한다.

- dummy 노드는 문제에서 주어진 head 이전에 무의미한 노드를 갖고 있는 연결 리스트를 말한다.  

- 이처럼 dummy 노드를 생성하는 이유는 삭제해야 하는 노드가 0번째(= 첫 번째) 노드인 경우를 위해서다.

 

- slow와 fast pointer의 거리를 n으로 유지한다.

- 예를 들어, n이 2라면 slow 포인터는 0번째 노드(= dummy)를 가리키고 fast 포인터는 2번째 노드를 가리키게 한다.

- 이 둘의 거리를 n으로 유지시킨 채로 fast.next가 null이 아닐 때까지 연결 리스트를 탐색한다.

 

- 이처럼 거리를 유지하고 탐색을 하는 이유는 다음과 같다.

- fast가 마지막 노드를 가리킬 때, slow는 연결 리스트의 뒤에서부터 n - 1번째 노드를 가리키게 된다. 

- slow노드를 기준으로, slow 노드의 다음 노드인 n번째 노드를 삭제하면 된다. 

 

- 다음 코드를 보면서 이해해보자. 

 

 

3. 정답 코드

a) Brute Force

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        ListNode first = head;
        int len = 1;
        
        while(first.next != null) {
            len++;
            first = first.next;
        }
        
        if(len == 1) return null;
        
        int target = len - n;
        if(target == 0) return head.next;
        
        first = head;
        for(int i = 0; i < target - 1; i++) {
            first = first.next;
        }
        
        first.next = first.next.next;
        return head;
    }
}

 

 

b) one path

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        
        ListNode slow = dummy;
        ListNode fast = dummy;
        
        while(fast.next != null) {
            fast = fast.next;
            if(n-- <= 0) {
                slow = slow.next;
            }
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}