📑 题目：82. 删除排序链表中的重复元素 II

🚀 本题 LeetCode 传送门

题目大意

删除链表中重复的结点，只要是有重复过的结点，全部删除。

解题思路

按照题意做即可。

代码

  1. package leetcode
  3. /**
  4.  * Definition for singly-linked list.
  5.  * type ListNode struct {
  6.  *     Val int
  7.  *     Next *ListNode
  8.  * }
  9.  */
  11. // 解法一
  12. func deleteDuplicates1(head *ListNode) *ListNode {
  13.  if head == nil {
  14.   return nil
  15.  }
  16.  if head.Next == nil {
  17.   return head
  18.  }
  19.  newHead := &ListNode{Next: head, Val: -999999}
  20.  cur := newHead
  21.  last := newHead
  22.  front := head
  23.  for front.Next != nil {
  24.   if front.Val == cur.Val {
  25.    // fmt.Printf(""相同节点front = %v | cur = %v | last = %v
  26. "", front.Val, cur.Val, last.Val)
  27.    front = front.Next
  28.    continue
  29.   } else {
  30.    if cur.Next != front {
  31.     // fmt.Printf(""删除重复节点front = %v | cur = %v | last = %v
  32. "", front.Val, cur.Val, last.Val)
  33.     last.Next = front
  34.     if front.Next != nil && front.Next.Val != front.Val {
  35.      last = front
  36.     }
  37.     cur = front
  38.     front = front.Next
  39.    } else {
  40.     // fmt.Printf(""常规循环前front = %v | cur = %v | last = %v
  41. "", front.Val, cur.Val, last.Val)
  42.     last = cur
  43.     cur = cur.Next
  44.     front = front.Next
  45.     // fmt.Printf(""常规循环后front = %v | cur = %v | last = %v
  46. "", front.Val, cur.Val, last.Val)
  48.    }
  49.   }
  50.  }
  51.  if front.Val == cur.Val {
  52.   // fmt.Printf(""相同节点front = %v | cur = %v | last = %v
  53. "", front.Val, cur.Val, last.Val)
  54.   last.Next = nil
  55.  } else {
  56.   if cur.Next != front {
  57.    last.Next = front
  58.   }
  59.  }
  60.  return newHead.Next
  61. }
  63. // 解法二
  64. func deleteDuplicates2(head *ListNode) *ListNode {
  65.  if head == nil {
  66.   return nil
  67.  }
  68.  if head.Next != nil && head.Val == head.Next.Val {
  69.   for head.Next != nil && head.Val == head.Next.Val {
  70.    head = head.Next
  71.   }
  72.   return deleteDuplicates(head.Next)
  73.  }
  74.  head.Next = deleteDuplicates(head.Next)
  75.  return head
  76. }
  78. func deleteDuplicates(head *ListNode) *ListNode {
  79.  cur := head
  80.  if head == nil {
  81.   return nil
  82.  }
  83.  if head.Next == nil {
  84.   return head
  85.  }
  86.  for cur.Next != nil {
  87.   if cur.Next.Val == cur.Val {
  88.    cur.Next = cur.Next.Next
  89.   } else {
  90.    cur = cur.Next
  91.   }
  92.  }
  93.  return head
  94. }
  96. // 解法三 双循环简单解法 O(n*m)
  97. func deleteDuplicates3(head *ListNode) *ListNode {
  98.  if head == nil {
  99.   return head
  100.  }
  102.  nilNode := &ListNode{Val: 0, Next: head}
  103.  head = nilNode
  105.  lastVal := 0
  106.  for head.Next != nil && head.Next.Next != nil {
  107.   if head.Next.Val == head.Next.Next.Val {
  108.    lastVal = head.Next.Val
  109.    for head.Next != nil && lastVal == head.Next.Val {
  110.     head.Next = head.Next.Next
  111.    }
  112.   } else {
  113.    head = head.Next
  114.   }
  115.  }
  116.  return nilNode.Next
  117. }
  119. // 解法四 双指针+删除标志位，单循环解法 O(n)
  120. func deleteDuplicates4(head *ListNode) *ListNode {
  121.  if head == nil || head.Next == nil {
  122.   return head
  123.  }
  125.  nilNode := &ListNode{Val: 0, Next: head}
  126.  // 上次遍历有删除操作的标志位
  127.  lastIsDel := false
  128.  // 虚拟空结点
  129.  head = nilNode
  130.  // 前后指针用于判断
  131.  pre, back := head.Next, head.Next.Next
  132.  // 每次只删除前面的一个重复的元素，留一个用于下次遍历判重
  133.  // pre, back 指针的更新位置和值比较重要和巧妙
  134.  for head.Next != nil && head.Next.Next != nil {
  135.   if pre.Val != back.Val && lastIsDel {
  136.    head.Next = head.Next.Next
  137.    pre, back = head.Next, head.Next.Next
  138.    lastIsDel = false
  139.    continue
  140.   }
  142.   if pre.Val == back.Val {
  143.    head.Next = head.Next.Next
  144.    pre, back = head.Next, head.Next.Next
  145.    lastIsDel = true
  146.   } else {
  147.    head = head.Next
  148.    pre, back = head.Next, head.Next.Next
  149.    lastIsDel = false
  150.   }
  151.  }
  152.  // 处理 [1,1] 这种删除还剩一个的情况
  153.  if lastIsDel && head.Next != nil {
  154.   head.Next = nil
  155.  }
  156.  return nilNode.Next
  157. }