【GoLang那点事】链表-删除排序链表中的重复元素，你能想到几种解法？

#### 问题 > 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字 #### 示例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的值，同理往后，我们看代码实现: ```go 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) } ``` * 构造两个切片，第一个存储链表节点的值，第二个存储需要组装新链表的元素在第一个切片中的下标 ``` go 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 } } ``` * 利用两个切片构造新的链表 ```go 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，继续循环。 ```go 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 } ``` #### 解法四 * 递归解决，代码量最少，但是递归一般难以理解，靠人脑演算是比较费劲的，递归本质就是利用了操作系统栈的能力，这里我画张图帮助大家理解  ```go 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那点事”，更多精彩期待你的到来**