82. 删除排序链表中的重复元素 II

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。返回同样按升序排列的结果链表。

复杂度分析

  • 时间复杂度：O(n)，其中 n 是链表的长度。

  • 空间复杂度：O(n)，栈的深度

    1. //递归，高级，就是通法，就是秀，就tm难想中间过程
    2. func deleteDuplicates(head *ListNode) *ListNode {
    3.   if head == nil || head.Next == nil {
    4.       return head
    5.   }
    6.   if head.Val == head.Next.Val {    //判断有重
    7.       for head.Next != nil && head.Val == head.Next.Val {    //判断的多重
    8.           head = head.Next    
    9.       }
    10.       return deleteDuplicates(head.Next)    //直接不要head，从下一跳再递归
    12.   } else {
    13.       head.Next = deleteDuplicates(head.Next)    //从下一跳前进，递归判断重复 
    14.       return head
    15.   }
    16. }

复杂度分析

  • 时间复杂度：O(n)，其中 n 是链表的长度。

  • 空间复杂度：O(1)。

    //迭代，双指针，哑结点,通法
func deleteDuplicates(head *ListNode) *ListNode {
  dummy := &ListNode{0,head}
  pre := dummy

  for head != nil && head.Next != nil {
      if head.Val == head.Next.Val {
          for head.Next != nil && head.Val == head.Next.Val {
              head.Next =head.Next.Next
          }
          pre.Next = head.Next         //放弃重复项! 核心一句1，带个指针，不然pre就断了   

      } else {                    //原来pre在head前一个，现在head=下一个head的pre
          pre = head                //非重复项，继续前进；未命中条件，核心一句2，有下一跳指针
      }
      head = head.Next             //head前进，原来的变pre
  }
  return dummy.Next
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是链表的长度。

  • 空间复杂度：O(1)。

    //单指针，迭代，就和哈希法差不多，存个值x
func deleteDuplicates(head *ListNode) *ListNode {
  if head == nil {
      return nil
  }

  dummy := &ListNode{0,head}
  pre := dummy

  for pre.Next != nil && pre.Next.Next != nil {
      if pre.Next.Val == pre.Next.Next.Val {
          x := pre.Next.Val    //记录重复值

          for pre.Next != nil && pre.Next.Val == x {    
              pre.Next = pre.Next.Next    //跳过cur=x点，这是重复项；因为for存在，会至少走两遍
          }
      } else {
          pre = pre.Next
      }
  }
  return dummy.Next
}