[LeetCode - 83] Remove Duplicates from Sorted List - Java

문제 설명

문제

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

 

입출력 예시

 

Input: head = [1,1,2]
Output: [1,2]

 

Input: head = [1,1,2,3,3]
Output: [1,2,3]

 

 

제한사항

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

 

풀이 : Success

소스 코드

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return null;
        ListNode first = head;
        int previous = head.val;
        while(head.next != null){
            if(head.next.val == previous) {
                ListNode listNode = new ListNode();
                listNode.next = head.next;
                head.next = listNode.next.next;
                listNode.next = null;
            }
            else {
                previous = head.next.val;
                head = head.next;
            }
        }

        return first;
    }
}​

 

풀이 회고

우선 연결리스트를 입력받으면 해당 연결리스트의 node 수가 0인 경우도 있으므로 null 체크한 이후 null을 반환하도록 했다.

 

이후 중복된 node 제거 작업 완료 후 최종 연결리스트를 반환하기 위해 처음 node 주소(head)를 별도로 저장해놓았다.(first)

 

중복 제거 작업을 하기 앞서 첫번째 node의 값을 previous 변수에 저장하도록 했는데, 이는 중복 유무를 검사하기 위한 용도이다. 해당 연결리스트를 끝까지 탐색하는 while 반복문에서 head 이후의 node의 값과 previous 값과 일치하는지 check하도록 했다.

 

만일 일치하는 경우 해당 node는 중복된 값을 가지고 있으므로 삭제하도록 했다. 삭제하고 나면 head가 가리키게 될 node는 삭제된 node 이후의 node가 되므로 이후 별다른 작업을 하지 않고 다음 while문을 돌면 된다.

 

만일 불일치하는 경우 해당 node는 삭제 대상이 아니고 건너 뛰어야 한다. 이때 다음 중복 검사를 위해 previous 값에 해당 node의 값을 저장하고 head가 해당 node 다음 node를 가리키도록 했다.

 

이러한 작업을 모두 마치면(while문 종료) 연결리스트의 첫 node를 가리키도록 했던 first(전체 연결리스트)를 반환하도록 했다.

 

모범 소스코드

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode curr = head;
        while(curr != null && curr.next!=null) {
            if(curr.next.val == curr.val) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }
        }
        return head;
    }
}​

 

코드 분석

위 풀이는 리트코드 내 수많은 모범 답안 중 하나이다. 기존 내 풀이 보다 훨씬 간결하다.

 

우선 입력받은 연결리스트에 대해서 별도 null 체크를 하지 않았는데, 이는 while 반복문의 조건식에서 해당 연결리스트의 null을 체크하고 있기 때문이다. 즉, 입력받은 연결리스트가 null이라면 while 반복문을 거치지 않고 그대로 null을 return할 것이다.

 

하지만 연결리스트의 크기 제한사항이 이 문제에서는 300이지만 훨씬 더 크다면? 그러면 그 개수에 비례해서 비교연산을 한 번 더 하게 되는 건데 굳이 while 반복문 조건식에 해당 조건을 넣어야 되는지 의문이다.

 

또한 중복 검사를 위해 별도 변수를 선언하지 않았고 현재 node의 값과 다음 node의 값을 바로 비교해주도록 했다. 사실 node에 바로 접근하면 되므로 굳이 중복검사를 위해 별도 변수를 선언할 필요가 없었다.

 

또한 나같은 경우 삭제 작업 시 새로운 노드를 생성하는 방식으로 삭제 시켜주었는데, 위 풀이처럼 삭제되기 직전 node가 다음 다음 node를 가리키도록 처리해주면 훨씬 효율적으로 삭제 처리를 시킬 수 있다. 이 부분은 위 코드와 같이 처리하는 것이 효율적으로 보인다.

 

개선된 나의 코드

사실 문제 자체가 연결리스트의 크기가 최대 300이므로 전후 코드의 성능차가 크지 않겠지만, 1ms 정도는 감축된 것을 확인할 수 있었다.

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return null;
        ListNode first = head;
        while(head.next != null){
            if(head.next.val == head.val) {
                head.next = head.next.next;
            }
            else {
                head = head.next;
            }
        }

        return first;
    }
}​

 

 

참고자료

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