Ming
0%

LeetCode-83

Posted on Edited on In

题目

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

结果

代码

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode p = head;
        //1-1-2-3-3
        while (p != null) {
            if (p.next != null) {
                if (p.next.val == p.val) {
                    p.next = p.next.next;
                } else {
                    p = p.next;
                }
            } else {
                 break;
            }
        }
        return head;
    }
}
  • Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
	set := make(map[int]bool)
	ans := &ListNode{Val: 0}
	p := ans
	for ptr := head; ptr != nil; ptr = ptr.Next {
		if _, ok := set[ptr.Val]; !ok {
			set[ptr.Val] = true
			p.Next = &ListNode{Val: ptr.Val}
			p = p.Next
		}
	}
	return ans.Next
}

复杂度

时间复杂度：O（n）

空间复杂度：O（1），Go的是O（n）