LeetCode: 82번 (Remove Duplicates from Sorted List II) [JAVA]

문제 링크

https://leetcode.com/problems/remove-duplicates-from-sorted-list/

Remove Duplicates from Sorted List - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 우선 주어진 전체 리스트를 한 번 돌며, 수가 반복되는 노드들에 대해 -9999로 값을 변경(최초 노드 제외)
2. 현재 노드가 유일한 노드인지를 판별하여, 해당 노드가 유일하지 않다면 다음 노드를 찾아주는 함수 findNext를 구현
   1) 해당 함수는 재귀적으로 구현하여, 반복되어 나타나는 중복 노드들을 모두 제거할 수 있도록 구현
3. 우선적으로 주어진 헤드노드에 대해 해당 함수를 호출
4. 이후 그 다음 노드부터, 반복적으로 findNext를 호출하며 전체 리스트에서 중복 노드들을 제거
5. 결과 헤더 노드 반환

 전체 리스트에서 중복되는 요소를 제거하는 문제이다. 다만 흔히 아는 중복 제거 문제와는 다른 점이, 중복이 발생하는 노드들을 하나도 남겨두지 않고 모두 제거해야 하는 문제이다.
 이를 위해 최소 한 번이라도 전체 리스트를 순회하며 중복되는 노드들을 체크해주어야 하는데, 이 때 리스트를 순회하며 중복되는 노드들에 -9999로 값을 변경해준다. 그 다음엔 하나의 함수를 구현하는데, 해당 함수는 주어진 노드가 유일한 노드인지 아닌지를 판별하여, 유일하지 않다면 해당 노드들을 모두 건너뛰고 다른 값이 오는 노드를 찾아 반환하는 함수이다. 이 때 함수를 재귀적으로 구성하여, 연속적으로 유일하지 않은 노드들이 와도 최종적으로는 유일한 노드(혹은 null)이 반환되도록 한다.
 해당 함수 구현이후엔, 전체 리스트에 대해 반복적으로 해당 함수를 호출해주면 된다. 우선 주어진 헤더노드에 대해서 해당 함수를 호출해 유일한 노드의 헤더노드를 찾은 다음, 그 이후 리스트 노드들에 대해서 해당 함수를 호출해 유일한 노드들로만 리스트가 구성되도록 해주면 된다. 해당 호출이 완성되면 해당 리스트의 헤더 노드를 반환해주면 된다.

 

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode temp = head;
        int prev = -9999;

        while (temp != null) {//전체 노드를 한 번 돌며, 이전과 중복되는 노드의 값을 변경
            if (temp.val == prev) {
                temp.val = -9999;
            } else {
                prev = temp.val;
            }
            temp = temp.next;
        }

        ListNode answer = findNext(head);//헤드에 대한 체크 진행
        temp = answer;

        while (temp != null) {//다음 노드들에 대해서도 중복 제거 진행
            temp.next = findNext(temp.next);
            temp = temp.next;
        }

        return answer;
    }

    ListNode findNext(ListNode node) {//다음에 올 노드를 탐색하는 함수
        if (node == null || node.next == null) {//현재 혹은 다음 노드가 null이라면
            return node;
        }

        if (node.next.val != -9999) {//다음 노드 값이 -9999가 아닌, 실제 값이 온다면 현재 노드는 유일한 노드
            return node;
        }

        ListNode next = node.next;

        while (next != null && next.val == -9999) {//-9999가 아닌 노드가 올 때까지 반복
            next = next.next;
        }

        return findNext(next);//해당 다음 노드에 대해서도 재귀로 다시 처리를 진행
    }
}

결과