중복값이 나오면 포인터를 리스트에서 빼는 문제이다. 요소를 Set 자료구조에 넣은 후,Set자료구조에 포함되면 이전포인터가 현재포인터를 건너띄고 다음포인터를 향하도록 하였다. 자바인데 컴파일러를 C로 했더니 계속 오류가 낫다 --
# Description
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.
Example 1:
Input: head = [1,1,2]
Output: [1,2]
Example 2:
Input: head = [1,1,2,3,3]
Output: [1,2,3]
#Solution
class Solution {
public ListNode deleteDuplicates(ListNode head) {
HashSet<Integer> values = new HashSet<>();
ListNode prev = null;
ListNode current = head;
while(current != null){
if(values.contains(current.val)){
prev.next = current.next; // set prev.next to skip the current node
}else{
values.add(current.val);
prev = current; // set the prev node to point the prev node
}
current = current.next; // move current node to the next node
}
return head;
}
}
I kept forgot the fact that this data strucutre is LinkedList. since prev is also become part of LinkedList. If i move next node of previous node to skip the current node. the whole LinkedList itself skips the current node !
In terms of space complexity, this algorithm uses only three constant variables (values,prev,current) . therefore space complexity is O(1) constant space time. On the other hand, In terms of time complexiy, it is O(n) leaner running time ,n represents the number of nodes in the linkedList
'Programming > LeetCode' 카테고리의 다른 글
[LeetCode] #88. Merge Sorted Array (repeat : 0) (0) | 2024.01.16 |
---|---|
[LeetCode] #1290 Convert Binary Number in a Linked List to Integer (repeat : 0) (0) | 2024.01.12 |
[LeetCode] #86 partition List (repeat : 0 ) (0) | 2024.01.07 |
[LeetCode] #9 Remove Nth Node From End of List (repeat:0) (1) | 2023.12.31 |
[LeetCode] #141 Linked List Cycle (repeat:1) (0) | 2023.12.25 |