알고리즘 - leetcode "remove-duplicates-from-sorted-list"

단일 연결리스트 중복 제거 문제 - https://leetcode.com/problems/remove-duplicates-from-sorted-list/

참고한 코드 - https://hyerios.tistory.com/250

다른 문제는 대부분 풀어보기도 했고, 어제 링크드리스트 문제를 제대로 해결하지 못해서 오늘은 이 문제만 집중해서 공부하고 풀어보았다.

어제 미션처럼 링크드리스트를 직접 구현하려고 하다가, 삽질을 너무 길게 해서 결국 구글링한 코드를 보고 정리했다.ㅠㅠ

주어진 연결리스트 구조

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
    }
}

생각한 것 보다 훨씬 단순하게 구현되어 있었다.

😇 가장 충격이었던 것은 포인터(next)로 자기 자신을 옵셔널로 가진다는 것...

첫 노드가 곧 헤드이고, .next로 다음 노드가 존재하는지 아닌지 확인해

있으면 다음 노드로 연결되고, 없으면 끝나는 식이다.

풀이 코드

/// 출처 : https://hyerios.tistory.com/250
func deleteDuplicates(_ head: ListNode?) -> ListNode? {
    var node = head // 첫 노드로 헤드만 가져옴
    
    while node?.next != nil { // 다음 노드가 없을 때까지 끝까지 반복
        while node?.val == node?.next?.val { // 현재 노드 값과 다음 노드 값이 같지 않을 때까지 반복
            node?.next = node?.next?.next // (값이 중복될 때)현재 노드의 포인터를 다음 노드의 포인터로 함
        }
        node = node?.next // 노드를 다음 노드로 치환
    }
    return head
    // return node가 아닌 이유 : node는 하나의 노드일 뿐 연결리스트 전체가 아님. 전체 연결리스트의 시작이자 작업이 반영된 head를 반환해야.
}