Merge pull request halfrost#69 from Janetyu/janetyu

halfrost · halfrost · commit 3e301996c952 · 2020-09-18T09:35:44.000+08:00
leetcode82 提供更多的解法
diff --git a/leetcode/0082.Remove-Duplicates-from-Sorted-List-II/82. Remove Duplicates from Sorted List II.go b/leetcode/0082.Remove-Duplicates-from-Sorted-List-II/82. Remove Duplicates from Sorted List II.go
@@ -91,3 +91,66 @@ func deleteDuplicates(head *ListNode) *ListNode {
 	}
 	return head
 }
+
+// 双循环简单解法 O(n*m)
+func deleteDuplicates3(head *ListNode) *ListNode {
+    if head == nil {
+        return head
+    }
+
+    nilNode := &ListNode{Val: 0, Next: head}
+    head = nilNode
+
+    lastVal := 0
+    for head.Next != nil && head.Next.Next != nil {
+        if head.Next.Val == head.Next.Next.Val {
+            lastVal = head.Next.Val
+            for head.Next != nil && lastVal == head.Next.Val {
+                head.Next = head.Next.Next
+            }
+        } else {
+            head = head.Next
+        }
+    }
+    return nilNode.Next
+}
+
+// 双指针+删除标志位，单循环解法 O(n)
+func deleteDuplicates4(head *ListNode) *ListNode {
+    if head == nil || head.Next == nil {
+        return head
+    }
+
+    nilNode := &ListNode{Val: 0, Next: head}
+    // 上次遍历有删除操作的标志位
+    lastIsDel := false
+    // 虚拟空结点
+    head = nilNode
+    // 前后指针用于判断
+    pre, back := head.Next, head.Next.Next
+    // 每次只删除前面的一个重复的元素，留一个用于下次遍历判重
+    // pre, back 指针的更新位置和值比较重要和巧妙
+    for head.Next != nil && head.Next.Next != nil {
+        if pre.Val != back.Val && lastIsDel {
+            head.Next = head.Next.Next
+            pre, back = head.Next, head.Next.Next
+            lastIsDel = false
+            continue
+        }
+
+        if pre.Val == back.Val {
+            head.Next = head.Next.Next
+            pre, back = head.Next, head.Next.Next
+            lastIsDel = true
+        } else {
+            head = head.Next
+            pre, back = head.Next, head.Next.Next
+            lastIsDel = false
+        }
+    }
+    // 处理 [1,1] 这种删除还剩一个的情况
+    if lastIsDel && head.Next != nil {
+        head.Next = nil
+    }
+    return nilNode.Next
+}
diff --git a/website/content/ChapterFour/0082.Remove-Duplicates-from-Sorted-List-II.md b/website/content/ChapterFour/0082.Remove-Duplicates-from-Sorted-List-II.md
@@ -43,6 +43,8 @@ package leetcode
  *     Next *ListNode
  * }
  */
+
+// 解法一
 func deleteDuplicates1(head *ListNode) *ListNode {
 	if head == nil {
 		return nil
@@ -89,6 +91,7 @@ func deleteDuplicates1(head *ListNode) *ListNode {
 	return newHead.Next
 }
 
+// 解法二
 func deleteDuplicates2(head *ListNode) *ListNode {
 	if head == nil {
 		return nil
@@ -103,4 +106,85 @@ func deleteDuplicates2(head *ListNode) *ListNode {
 	return head
 }
 
+func deleteDuplicates(head *ListNode) *ListNode {
+	cur := head
+	if head == nil {
+		return nil
+	}
+	if head.Next == nil {
+		return head
+	}
+	for cur.Next != nil {
+		if cur.Next.Val == cur.Val {
+			cur.Next = cur.Next.Next
+		} else {
+			cur = cur.Next
+		}
+	}
+	return head
+}
+
+// 解法三 双循环简单解法 O(n*m)
+func deleteDuplicates3(head *ListNode) *ListNode {
+    if head == nil {
+        return head
+    }
+
+    nilNode := &ListNode{Val: 0, Next: head}
+    head = nilNode
+
+    lastVal := 0
+    for head.Next != nil && head.Next.Next != nil {
+        if head.Next.Val == head.Next.Next.Val {
+            lastVal = head.Next.Val
+            for head.Next != nil && lastVal == head.Next.Val {
+                head.Next = head.Next.Next
+            }
+        } else {
+            head = head.Next
+        }
+    }
+    return nilNode.Next
+}
+
+// 解法四 双指针+删除标志位，单循环解法 O(n)
+func deleteDuplicates4(head *ListNode) *ListNode {
+    if head == nil || head.Next == nil {
+        return head
+    }
+
+    nilNode := &ListNode{Val: 0, Next: head}
+    // 上次遍历有删除操作的标志位
+    lastIsDel := false
+    // 虚拟空结点
+    head = nilNode
+    // 前后指针用于判断
+    pre, back := head.Next, head.Next.Next
+    // 每次只删除前面的一个重复的元素，留一个用于下次遍历判重
+    // pre, back 指针的更新位置和值比较重要和巧妙
+    for head.Next != nil && head.Next.Next != nil {
+        if pre.Val != back.Val && lastIsDel {
+            head.Next = head.Next.Next
+            pre, back = head.Next, head.Next.Next
+            lastIsDel = false
+            continue
+        }
+
+        if pre.Val == back.Val {
+            head.Next = head.Next.Next
+            pre, back = head.Next, head.Next.Next
+            lastIsDel = true
+        } else {
+            head = head.Next
+            pre, back = head.Next, head.Next.Next
+            lastIsDel = false
+        }
+    }
+    // 处理 [1,1] 这种删除还剩一个的情况
+    if lastIsDel && head.Next != nil {
+        head.Next = nil
+    }
+    return nilNode.Next
+}
+
 ```
