Linked List | Remove Duplicates from Sorted List

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.

이미 숫자로 정렬되어있는 Linked List에서 중복되는 값을 가진 노드들을 삭제한 후, 다시 Linked List를 리턴하라는 문제이다. 리턴시에는 그 리스트의 Head를 리턴하면 된다. 이 문제는 한번의 loop으로 해결할 수 있다.

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

* Time Complexity: O(N)
* Space Complexity: O(1)

1번의 loop을 돌면서, pivot으로 지정해둔 노드의 값과 다른값을 나둘때까지 curr를 옮기고, 다른값을 만나면 next로 지정해준 후, pivot을 옮겨주는 방법이다. while loop이 깨진 후 pivot의 next값을 지정해주는 이유는, 같은 숫자가 계속 이어지다가 while loop을 빠져나온 경우를 위해서이다. 이 방법으로 했을 때, 아래와같이 최상위의 Runtime, 61.17%의 메모리 사용을 했다. 

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

* Time Complexity: O(N)
* Space Complexity: O(1)

Pivot이 없이 진행하는 방법도 있다. loop 안에서 만약 값이 같으면, curr노드의 next 값을 curr.next.next노드로 지정해주는 방식이다. 코드 라인 수가 훨씬 적다. 이 방식으로 했을때, Run time은 비슷했으나 조금의 메모리를 훠씬 많이 사용했다. 

 

 

높은 CP부터 정리되어있는 뮤츠. 중복이 있는 CP의 뮤츠를 지우면? 지워진 뮤츠 자리에 그 다음 뮤츠가 오게된다.

 

 

 

Reference

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

Remove Duplicates from Sorted List - LeetCode