创建时间： 2019/7/29 20:07
作者： sunpengwei1992@aliyun.com

问题

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字

示例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的值，同理往后，我们看代码实现:

    1. type ListNode struct {
    2.   Val int
    3.   Next *ListNode
    4. }
    5. func deleteDuplicates(head *ListNode) *ListNode {
    6.   if head == nil{
    7.       return nil  
    8.   }
    9.   //构造两个切片存放上面思路说的数据
    10.   slice1,slice2 := buildTwoSlice(head)
    11.   //构造返回结果的链表
    12.   return buildRsult(slice1,slice2)
    13. }

  • 构造两个切片，第一个存储链表节点的值，第二个存储需要组装新链表的元素在第一个切片中的下标

    1. func buildTwoSlice( head *ListNode)([]int,[]int){
    2.   slice1 := make([]int,0,0)
    3.   slice2 := make([]int,0,0)
    4.   current := head.Val
    5.   i, v := 0,0
    6.   for head != nil{
    7.       temp := head.Val
    8.       slice1 = append(slice1,temp)
    9.       v++
    10.       //如果当前值和原来值一样
    11.       if temp == current{
    12.           //如果切片的大小是0，说明第一次
    13.          if len(slice2)==0{
    14.               slice2 = append(slice2,v)
    15.          }else{
    16.               //否则原来下标处的值+1
    17.               slice2[i] = v
    18.          }
    19.       }else{
    20.           //当前值和原来值不一样,往切片新增,下标+1
    21.           slice2 = append(slice2,v)
    22.           i++
    23.       }
    24.       //修改当前值
    25.       current = temp
    26.       head = head.Next
    27.   }
    28. }

  • 利用两个切片构造新的链表

    1. func buildResult(slice1,slice2 []int) *ListNode{
    2.   temp := &ListNode{0,nil}
    3.   result := temp
    4.   //组装一个新的链表
    5.   for i,v := range slice2{
    6.       if i ==0 && v != 1{
    7.           continue
    8.       }
    9.       if i ==0 && v ==1{
    10.           temp.Next = &ListNode{slice1[v-1],nil}
    11.           temp = temp.Next
    12.           continue
    13.       }
    14.       if v - slice2[i-1] ==1{
    15.           temp.Next = &ListNode{slice1[v-1],nil}
    16.           temp = temp.Next
    17.       }
    18.   }
    19.   return result.Next
    20. }

    解法三

  • 看了解法二，发现代码量也挺多的，好难受，我想少写点代码，能不能不用声明两个数组啊（占用内存多了），我们使用O(1)的空间复杂度可以吗？我们在遍历链表的时候，用链表下一个节点的值和当前节点的值比较，如果不一样，把当前节点加入新的链表，否则继续一下比较，这里一个点需要注意，就是如果一样，其实下一个节点的值也是不加入链表的，怎么办呢，我们利用一个临时变量 falg，开始值为fasle，当出现一样时，falg改为true,在下一次比较时，如果不一样，则falg是否为true，是的话，则忽略，将falg改为false，继续循环。

    1. type ListNode struct {
    2.   Val int
    3.   Next *ListNode
    4. }
    5. func deleteDuplicates(head *ListNode) *ListNode {
    6.   if head == nil{
    7.       return nil  
    8.   }
    9.   //创建一个临时链表
    10.   temp := &ListNode{0,nil} 
    11.   //将指针指向返回值
    12.   result := temp
    13.   //临时变量用来标记当前节点和next节点相等时，next节点也不加入临时链表
    14.   falg := false
    15.   for head != nil{
    16.       next := head.Next
    17.       //如果next为空或者不相等
    18.       if next == nil || next.Val != head.Val{
    19.           //先判断falg
    20.           if falg{
    21.               falg = false
    22.           }else{
    23.               //否则构造临时链表
    24.               temp.Next = &ListNode{head.Val,nil}
    25.               temp = temp.Next
    26.           }
    27.           //else表示相等
    28.       }else{
    29.            falg = true
    30.       }
    31.       head = head.Next
    32.   }
    33.   return result.Next
    34. }

    解法四

  • 递归解决，代码量最少，但是递归一般难以理解，靠人脑演算是比较费劲的，递归本质就是利用了操作系统栈的能力，这里我画张图帮助大家理解

链表-删除排序链表中的重复元素，你能想到几种解法？ - 图1

  1. func deleteDuplicates(head *ListNode) {
  2.     if head == nil{
  3.         return head;
  4.     }
  5.     //判断节点的next不为空，并且当前节点等于next节点
  6.     if head.Next != nil && head.Val == head.Next.Val{
  7.         //循环直到当前节点不等于next节点
  8.         for head.Next != nil && head.Val == head.Next.Val{
  9.             head = head.Next
  10.         }
  11.         //这时相当于去重剩余的链表
  12.         return deleteDuplicates(head.Next)
  13.     }else{
  14.         //否则将去重后的节点赋值给head.Next节点
  15.         head.Next = deleteDuplicates(head.Next)
  16.     }
  17.     return head
  18. }

欢迎大家关注微信公众号：“golang那点事”，更多精彩期待你的到来
GoLang公众号.jpg