Remove Duplicates from Sorted List - LeetCode

Problem

1. input: 연결 리스트의 첫 노드 head
2. output: 연결 리스트의 모든 중복 값을 가진 노드를 없앤 후 head 리턴
   • 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.

Idea

주어진 연결 리스트는 오름차순 정렬된 상태이므로 한번의 탐색으로 중복된 값을 삭제해주면 된다 → Sol1

Solution

1. 탐색

   커서를 이동하면서 다음값과 현재 값이 같은 경우 다음 값 삭제

   /**
    * Example:
    * var li = ListNode(5)
    * var v = li.`val`
    * Definition for singly-linked list.
    * class ListNode(var `val`: Int) {
    *     var next: ListNode? = null
    * }
    */
   class Solution {
       fun deleteDuplicates(head: ListNode?): ListNode? {
           var cursor = head
   
           while (cursor != null && cursor!!.next != null) {
               if (cursor!!.`val` == cursor!!.next!!.`val`) { // 중복된 값
                   cursor!!.next = cursor!!.next!!.next // 중복된 노드 삭제
               } else {
                   cursor = cursor!!.next
               }
           }
   
           return head
       }
   }
   

   시간 복잡도: 연결 리스트 탐색 = n

   

Point