删除链表中的重复元素

题目描述

给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。

测试用例

用例一

输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]

用例二

输入:head = [1,1,1,2,3]
输出:[2,3]

实现方案

递归实现

  • 因为题目给出的是已排序的数组,则重复元素必然连续,故一次处理即可删除重复元素
  • 如果 head == nil 或者 head.Next == nil 则直接返回head即可
  • 如果 head.Val != head.Next , 则 head.Next = deleteDuplicates(head) , 向后迭代即可
  • 如果 head.Val != head.Next, 则一直向后移动指针move, 直至 head.Val != move.Val 为止, 并返回 deleteDuplicates(head)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// ListNode Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}

func deleteDuplicates(head *ListNode) *ListNode {
if nil == head {
return nil
}
if nil == head.Next {
return head
}
if head.Next.Val != head.Val {
head.Next = deleteDuplicates(head.Next)
} else {
// 相等. 直到找到不相等的位置
move := head.Next
for move != nil && move.Val == head.Val {
move = move.Next
}
return deleteDuplicates(move)
}
return head
}

迭代实现

小技巧 -> 哑节点 :
要对头结点进行操作时,考虑创建哑节点dummy,使用dummy->next表示真正的头节点。这样可以避免处理头节点为空的边界问题。

  • 新建哑节点, 作为头节点, 降低 对头节点操作的复杂度, 最终返回 dummy.Next 即可
  • 开始迭代, 若当前节点下一个节点和下下一个节点值相等,记录当前值为待比较的值。
  • 指针后移, 反复修改当前节点的Next指向, 直至当前节点值下一个节点值和待比较值不一致
  • 若当前节点下一个节点和下下一个节点值不想等, 当前节点直接设置为 cur.Next , 无需变更指针指向关系
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func deleteDuplicates(head *ListNode) *ListNode {
dummy := &ListNode{
Val: 0,
Next: head,
}
cur := dummy
for cur.Next != nil && cur.Next.Next != nil {
if cur.Next.Val == cur.Next.Next.Val {
compareVal := cur.Next.Val
for cur.Next != nil && cur.Next.Val == compareVal {
cur.Next = cur.Next.Next
}
} else {
cur = cur.Next
}
}
return dummy.Next
}

删除链表中的重复元素
http://go.zhangdeman.cn/archives/a4cb7384.html
作者
白茶清欢
发布于
2022年6月29日
许可协议