add leetcode 82

saenaii · saenaii · commit d6aaf42d538e · 2019-06-03T21:33:46.000+08:00
diff --git a/src/0082.Remove-Duplicates-from-Sorted-List-II/ListNode.go b/src/0082.Remove-Duplicates-from-Sorted-List-II/ListNode.go
@@ -0,0 +1,61 @@
+package Solution
+
+import (
+	"fmt"
+	"math/rand"
+)
+
+type ListNode struct {
+	Val  int
+	Next *ListNode
+}
+
+//	比较结果
+func isEqual(l1 *ListNode, l2 *ListNode) bool {
+
+	for l1 != nil && l2 != nil {
+		if l1.Val != l2.Val {
+			return false
+		}
+		l1 = l1.Next
+		l2 = l2.Next
+	}
+	if l1 == nil && l2 != nil {
+		return false
+	}
+	if l1 != nil && l2 == nil {
+		return false
+	}
+	return true
+}
+
+func PrintList(head *ListNode) {
+	for head != nil {
+		fmt.Print(head.Val, "->")
+		head = head.Next
+	}
+	fmt.Println()
+}
+
+// 根据数组反序列化链表
+func UnmarshalListBySlice(nums []int) *ListNode {
+	head := &ListNode{Val: -1, Next: nil}
+	tmp := head
+	for _, v := range nums {
+		tmp.Next = &ListNode{Val: v, Next: nil}
+		tmp = tmp.Next
+	}
+	return head.Next
+}
+
+// 随机初始化链表
+func UnmarshalListByRand(max_num int, len int) *ListNode {
+	head := &ListNode{Val: -1, Next: nil}
+	tmp := head
+
+	for i := 0; i < len; i++ {
+		tmp.Next = &ListNode{Val: rand.Intn(max_num), Next: nil}
+		tmp = tmp.Next
+	}
+	return head.Next
+}
diff --git a/src/0082.Remove-Duplicates-from-Sorted-List-II/README.md b/src/0082.Remove-Duplicates-from-Sorted-List-II/README.md
@@ -1,34 +1,33 @@
-# [1. Add Sum][title]
+# [82. Remove Duplicates from Sorted List II[title]
 
 ## Description
 
-Given two binary strings, return their sum (also a binary string).
-
-The input strings are both **non-empty** and contains only characters `1` or `0`.
+Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
 
 **Example 1:**
 
 ```
-Input: a = "11", b = "1"
-Output: "100"
+Input: 1->2->3->3->4->4->5
+Output: 1->2->5
 ```
 
 **Example 2:**
 
 ```
-Input: a = "1010", b = "1011"
-Output: "10101"
+Input: 1->1->1->2->3
+Output: 2->3
 ```
 
-**Tags:** Math, String
+**Tags:** Linked List
 
 ## 题意
->给你两个二进制串，求其和的二进制串。
+> 给定一个有序的单链表，删除其中的重复元素。
 
 ## 题解
 
 ### 思路1
-> 按照小学算数那么来做，用 `carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
+> 使用两个指针，一个指针指向当前元素，另一个指针指向前一个元素。
+> 不断判断当前元素和下一个元素是否相等，如果相等，当前元素指向下一个，否则，令前一个指针指向当前节点的下一个节点。
 
 ```go
 
@@ -44,5 +43,5 @@ Output: "10101"
 
 如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
 
-[title]: https://leetcode.com/problems/two-sum/description/
+[title]: https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/
 [me]: https://github.com/kylesliu/awesome-golang-leetcode
diff --git a/src/0082.Remove-Duplicates-from-Sorted-List-II/Solution.go b/src/0082.Remove-Duplicates-from-Sorted-List-II/Solution.go
@@ -1,5 +1,36 @@
 package Solution
 
-func Solution(x bool) bool {
-	return x
+/*
+ * @lc app=leetcode id=82 lang=golang
+ *
+ * [82] Remove Duplicates from Sorted List II
+ */
+/**
+ * Definition for singly-linked list.
+ * type ListNode struct {
+ *     Val int
+ *     Next *ListNode
+ * }
+ */
+func Solution(head *ListNode) *ListNode {
+	if nil == head || nil == head.Next {
+		return head
+	}
+	p := new(ListNode)
+	p.Next = head
+	prev, current := p, p.Next
+	for current != nil && current.Next != nil {
+		if current.Val == current.Next.Val {
+			for current.Next != nil && current.Val == current.Next.Val {
+				current = current.Next
+			}
+			current = current.Next
+			prev.Next = current
+		} else {
+			prev = prev.Next
+			current = current.Next
+		}
+	}
+	return p.Next
 }
+
diff --git a/src/0082.Remove-Duplicates-from-Sorted-List-II/Solution_test.go b/src/0082.Remove-Duplicates-from-Sorted-List-II/Solution_test.go
@@ -1,29 +1,36 @@
 package Solution
 
 import (
-	"reflect"
 	"testing"
 )
 
 func TestSolution(t *testing.T) {
 	//	测试用例
 	cases := []struct {
 		name   string
-		inputs bool
-		expect bool
+		inputs []int
+		expect []int
 	}{
-		{"TestCacse 1", true, true},
-		{"TestCacse 1", true, true},
-		{"TestCacse 1", false, false},
+		{
+			"TestCase 1",
+			[]int{1,2,3,3,4,4,5},
+			[]int{1,2,5},
+		},
+		{
+			"TestCase 2",
+			[]int{1,1,1,2,3},
+			[]int{2,3},
+		},
 	}
 
 	//	开始测试
 	for _, c := range cases {
 		t.Run(c.name, func(t *testing.T) {
-			ret := Solution(c.inputs)
-			if !reflect.DeepEqual(ret, c.expect) {
-				t.Fatalf("expected: %v, but got: %v, with inputs: %v",
-					c.expect, ret, c.inputs)
+			ret := Solution(UnmarshalListBySlice(c.inputs))
+			if !isEqual(ret, UnmarshalListBySlice(c.expect)) {
+				PrintList(ret)
+				PrintList(UnmarshalListBySlice(c.expect))
+				t.Fatalf("expected: %v, but got: %v, with inputs: %v", c.expect, ret, c.inputs)
 			}
 		})
 	}
