链表-删除排序链表中的重复元素，你能想到几种解法？
问题
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字
示例1
输入: 1->2->3->3->4->4->5 输出: 1->2->5
示例二
输入: 1->1->1->2->3 输出: 2->3
解法一
- 提取问题关键字，有序链表，删除重复，因为是有序的，所以重复的元素一定相邻的，不会出现（2->3-2）这种情况的，最简单的办法，遍历链表，利用数据结构map,key是链表节点的值，value是值在链表中出现的次数，最终次数大于1的就是重复的，等于1的就是不重复的，但是map元素是无序的，所以我们对剩余的元素排序，最后转化为链表。
- 麻烦吗？我觉得很麻烦，也没人这么实现。看到上面给的算法我就不想写代码，所以呢，不写了，看解法二。
解法二
- 上面我们提到了map，又遍历，又去重，又排序，又构造，很累，有没有简单一点呢?
- 我们在遍历链表时，创建两个数组，第一个数组存储链表元素的值，第二个数组存储元素出现的次数，以此往后递加，举个例子吧：
- 链表：1->1->1->2->3
- 数组1：[1][1][1][2][3]
- 数组2：[3][4][5]
- 主要看第二个数组，元素1出现了三次，数组下标0的值是3，元素2出现了一次，所以数组下标1的值是3+1=4，同理数组下标2的值是4+1=5
- 最后我们遍历数组二，数组二下标0的值大于1，说明有重复，数组二下标1的值减下标0的值等于1，说明没重复，则取数组1的下标4-1的值，同理往后，我们看代码实现:
type ListNode struct {
Val int
Next *ListNode
}
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil{
return nil
}
//构造两个切片存放上面思路说的数据
slice1,slice2 := buildTwoSlice(head)
//构造返回结果的链表
return buildRsult(slice1,slice2)
}- 构造两个切片，第一个存储链表节点的值，第二个存储需要组装新链表的元素在第一个切片中的下标
func buildTwoSlice( head *ListNode)([]int,[]int){
slice1 := make([]int,0,0)
slice2 := make([]int,0,0)
current := head.Val
i, v := 0,0
for head != nil{
temp := head.Val
slice1 = append(slice1,temp)
v++
//如果当前值和原来值一样
if temp == current{
//如果切片的大小是0，说明第一次
if len(slice2)==0{
slice2 = append(slice2,v)
}else{
//否则原来下标处的值+1
slice2[i] = v
}
}else{
//当前值和原来值不一样,往切片新增,下标+1
slice2 = append(slice2,v)
i++
}
//修改当前值
current = temp
head = head.Next
}
}- 利用两个切片构造新的链表
func buildResult(slice1,slice2 []int) *ListNode{
temp := &ListNode{0,nil}
result := temp
//组装一个新的链表
for i,v := range slice2{
if i ==0 && v != 1{
continue
}
if i ==0 && v ==1{
temp.Next = &ListNode{slice1[v-1],nil}
temp = temp.Next
continue
}
if v - slice2[i-1] ==1{
temp.Next = &ListNode{slice1[v-1],nil}
temp = temp.Next
}
}
return result.Next
}解法三
- 看了解法二，发现代码量也挺多的，好难受，我想少写点代码，能不能不用声明两个数组啊（占用内存多了），我们使用O(1)的空间复杂度可以吗？我们在遍历链表的时候，用链表下一个节点的值和当前节点的值比较，如果不一样，把当前节点加入新的链表，否则继续一下比较，这里一个点需要注意，就是如果一样，其实下一个节点的值也是不加入链表的，怎么办呢，我们利用一个临时变量 falg，开始值为fasle，当出现一样时，falg改为true,在下一次比较时，如果不一样，则falg是否为true，是的话，则忽略，将falg改为false，继续循环。
type ListNode struct {
Val int
Next *ListNode
}
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil{
return nil
}
//创建一个临时链表
temp := &ListNode{0,nil}
//将指针指向返回值
result := temp
//临时变量用来标记当前节点和next节点相等时，next节点也不加入临时链表
falg := false
for head != nil{
next := head.Next
//如果next为空或者不相等
if next == nil || next.Val != head.Val{
//先判断falg
if falg{
falg = false
}else{
//否则构造临时链表
temp.Next = &ListNode{head.Val,nil}
temp = temp.Next
}
//else表示相等
}else{
falg = true
}
head = head.Next
}
return result.Next
}解法四
- 递归解决，代码量最少，但是递归一般难以理解，靠人脑演算是比较费劲的，递归本质就是利用了操作系统栈的能力，这里我画张图帮助大家理解.
func deleteDuplicates(head *ListNode) {
if head == nil{
return head;
}
//判断节点的next不为空，并且当前节点等于next节点
if head.Next != nil && head.Val == head.Next.Val{
//循环直到当前节点不等于next节点
for head.Next != nil && head.Val == head.Next.Val{
head = head.Next
}
//这时相当于去重剩余的链表
return deleteDuplicates(head.Next)
}else{
//否则将去重后的节点赋值给head.Next节点
head.Next = deleteDuplicates(head.Next)
}
return head
}欢迎大家关注微信公众号：“golang那点事”，更多精彩期待你的到来
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-07-31，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
