82. Remove Duplicates from Sorted List II
Tags:
Medium
Skills:
Linked List
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu xóa tất cả các node có giá trị bị lặp trong một linked list đã được sắp xếp, chỉ giữ lại các node có giá trị xuất hiện đúng một lần.
Ví dụ: với input 1->2->3->3->4->4->5, output sẽ là 1->2->5 vì các giá trị 3 và 4 bị lặp nên bị loại bỏ hoàn toàn
Approach
node đầu cũng bị loại bỏ, ta nên dùng một node giả (dummy node) trỏ vào đầu danh sáchprev : Trỏ tới node cuối cùng của danh sách kêt quả (không bị trùng)current : Duyệt qua các node của danh sáchQuy trình
current.val===current.next.val ), di chuyển current đến node cuối cùng của nhóm đóprev.next === current ), di chuyển prev tới node tiếp theoprev.next = current.next current tới node tiếp theoTime and space complexity
Solution
1/**
2 * Definition for singly-linked list.
3 * class ListNode {
4 * val: number
5 * next: ListNode | null
6 * constructor(val?: number, next?: ListNode | null) {
7 * this.val = (val===undefined ? 0 : val)
8 * this.next = (next===undefined ? null : next)
9 * }
10 * }
11 */
12
13function deleteDuplicates(head: ListNode | null): ListNode | null {
14 const dummy = new ListNode(0, head);
15 let prev = dummy;
16 let curr = head;
17 while (curr) {
18 let has_dup = false
19 while (curr.next && curr.val === curr.next.val) {
20 has_dup = true;
21 curr = curr.next
22 }
23
24 if (has_dup) {
25 prev.next = curr.next
26 } else {
27 prev = prev.next
28 }
29
30 curr = curr.next;
31 }
32
33 return dummy.next;
34};