LeetCode 82. 删除排序链表中的重复元素 II
题目描述
思路分析
- 使用一个虚拟头节点（dummy node）来处理头节点可能被删除的情况。
- 使用两个指针 pre 和 cur，pre 指向当前不重复的最后一个节点，cur 用来遍历链表。
- 如果 cur 和 cur.Next 的值相同，则继续向后遍历，直到找到不同的值，然后将 pre.Next 指向这个不同的值。
- 如果 cur 和 cur.Next 的值不同，则将 pre 移动到 cur。
- 继续遍历直到链表结束。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func deleteDuplicates(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
pre := dummy
cur := head
for cur != nil {
// 如果当前节点和下一个节点的值相同
if cur.Next != nil && cur.Val == cur.Next.Val {
// 跳过所有重复的节点
for cur.Next != nil && cur.Val == cur.Next.Val {
cur = cur.Next
}
// 将 pre 的 Next 指向下一个不重复的节点
pre.Next = cur.Next
} else {
// 如果当前节点和下一个节点的值不同
pre = pre.Next
}
cur = cur.Next
}
return dummy.Next
}
- 时间复杂度: O (n)，其中 n 是链表的长度。我们只需要遍历链表一次。
- 空间复杂度: O (1)，我们只使用了常数级别的额外空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode();
dummy.next = head;
ListNode pre = dummy;
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.next.val == cur.val) {
while (cur.next != null && cur.next.val == cur.val) {
cur = cur.next;
}
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return dummy.next;
}
}
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！