LeetCode알고리즘 Remove Duplicates from Sorted List

오늘은 83번 문제를 풀어보겠습니다.
EASY고 현재는 47.9%의 성공률을 보이네요.

 

오늘 주제는 Linked List입니다. 

정렬된 링크드 리스트의 헤드가 주어지면, 중복되는 것들을 지워서 각 원소들이 한 번씩만 나타나게 해라. 

 

주어진 예시들을 보겠습니다.

1번 예시를 보면, 1이 2번 나왔잖아요.
그래서 1노드 한 개를 지워줍니다. 
지운 결과는 [1,2]이 됩니다.

 

2번 예시를 보면, 1이 2번 2가 1번, 3이 2번 나왔습니다.
그럼 1노드 1개 지워주고 3노드 1개 지워줘야겠죠.
지운 결과는 [1,2,3]이 됩니다.

 

문제에서 주어진 제약조건들을 살펴보면
노드의 수, node의 value값, 정렬 보장이 적혀있네요.  

마지막 문장이 가장 눈에 띄네요.
일단 정렬이 보장되니까 이 문제는 쉽게 접근할 수 있습니다.

 

+ 제공해주는 ListNode클래스

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */

 

 

class Solution {
    func deleteDuplicates(_ head: ListNode?) -> ListNode? {
        var temp = head
        
        while temp?.next != nil {            
            while temp?.val == temp?.next?.val {
                temp?.next = temp?.next?.next
            }
            temp = temp?.next
        }
        
        return head
    }
}

먼저 temp를 생성해줍니다.
while문을 돌면서 temp?.next가 nil이 아닐 때까지 돕니다.
내부에 있는 while문을 통해서 temp?.val이랑 temp?.next?.val이 같으면 temp?.next?.next를 temp?.next에 넣어줍니다.
이 작업을 통해서 값이 같지 않을 때 까지 돌아서 val이 중복되는 노드를 제거하게 됩니다.
(포인팅 하는 노드를 변경하는거니까 제거는 아니고,, 제거된 것 처럼 보이게 함)
그리고 내부의 while을 나오면 temp는 temp?.next로 변경해줍니다.
그리고 head를 리턴해줍니다.

 

1번 예시 과정ㅋㅋ
(발로 그린 것 같네요,,, ㅈㅅ)

이렇게 했을 때 결과

메모리 사용량 왜그럼?
뭘 많이 사용한 것 같지도 않은데...

 

---

+ 추가

class Solution {
    func deleteDuplicates(_ head: ListNode?) -> ListNode? {
        var temp = head
        
        while temp != nil {     
            if temp?.val == temp?.next?.val {
                temp?.next = temp?.next?.next
            } else {
                temp = temp?.next
            }
        }
        
        return head
    }
}

이렇게 푸는 방법도 있습니다.
temp?.next = temp?.next?.next 여기를 실행하는 횟수는 위 코드와 동일합니다.
그래서인지 시간 복잡도는 비슷하더라구요.
개인적으로는 처음 작성한 코드가 더 직관적으로 느껴진다고 판단해 윗 방법을 선택했습니다.

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