LeetCode 203(Removed Linked List Elements, java)

0. 문제

https://leetcode.com/problems/remove-linked-list-elements/

Remove Linked List Elements - LeetCode

 

1. 문제 설명

- 문제에서 연결 리스트(head)와 찾고자 하는 값(val)이 주어진다.

- 이 문제의 핵심은 연결 리스트 내부의 모든 노드 중 찾고자 하는 값과 동일한 value를 가진 노드를 삭제하는 것이다.

 

2. 문제 해설

a) 첫 번째 접근

- 연결 리스트를 탐색하기 위해서 연결 리스트의 가장 첫 번째 노드(head)를 참조하는 새 연결 리스트(result)를 생성한다.

- result의 첫 번째 노드는 -1의 value를 갖으며, 두 번째 노드부터 head를 참조하도록 설정한다.

- result는 마지막에 반환 값으로 사용될 예정이다.

 

- 여기서 result의 첫 번째 노드를 -1로 설정하는 이유는 head의 첫 번째 노드가 삭제 대상인 경우를 대비하기 위함이다.

- 문제에서 주어진 ListNode 클래스는 next 속성을 이용하여 다음 노드만 접근할 수 있다.

 

- 그러므로 현재 접근한 노드가 삭제 대상인 경우, 이전 노드에 접근할 수 있는 방법이 없다.  

- 즉, 이전 노드로 접근이 불가능하기에 현재 노드를 이전 노드처럼 사용해야 하기 위함이다.

 

- 즉, 이 문제를 풀기 위해서는 다음 노드의 value가 찾고자 하는 값(val)과 동일한 경우일 때만 찾을 수 있다. 

 

- result의 첫 번째 노드를 굳이 -1로 값을 설정하는 이유는, 문제의 제약에서 val의 범위가 0 ~ 50 사이의 값이기 때문이다.

- 그러므로 탐색의 대상에서 제외하기 위함이다. (사실, 탐색 과정에서 아예 배제되는 노드이기도 하다.)

 

b) 두 번째 접근

- 이제 result를 탐색하기 위한 새 연결 리스트(temp)를 생성한다. 

- temp의 가장 첫 번째 노드는 result를 참조하도록 설정한다. 

 

- temp가 필요한 이유는 다음과 같다.

  → result를 이용하여 탐색하는 경우, result.next를 사용해야 한다.

  → 이렇게 탐색하여 대상 노드를 모두 삭제하고 나면, 반환 시 가장 마지막으로 탐색한 노드가 반환된다. 

  → 즉, 시작 노드가 반환되는 것이 아니라 가장 마지막 노드가 반환된다. 

 

- 이와 같은 이유로, 새로운 연결 리스트(temp)를 생성하여 result를 참조하도록 설정한다. 

 

c) 세 번째 접근 

- 이제 모든 준비는 끝났다.

- 연결 리스트(temp)를 이용하여 탐색을 진행한다. 

- 어떤 노드의 다음 노드가 찾고자 하는 값(val)과 동일한 value를 가진 경우, 이를 삭제한다.

- 그리고 현재 노드와 삭제된 노드의 다음 노드를 이어준다.

 

3. 정답 코드

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        
        if(head == null) {return head;}
        
        ListNode result = new ListNode(-1);
        result.next = head;
        ListNode temp = result;
        
        while(temp.next != null) {
            if(temp.next.val == val) {
                ListNode node = temp.next.next;
                temp.next = null;
                temp.next = node;
            }
            else {temp = temp.next;}  
        }
        return result.next;
    }
}