LeetCode 82 删除排序链表中的重复元素 II
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/
博主Github:https://github.com/GDUT-Rp/LeetCode
题目:
给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。
示例1:
输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]
示例2:
输入:head = [1,1,1,2,3]
输出:[2,3]
提示:
- -100 <= Node.val <= 100
- 链表中节点数目在范围 [0, 300] 内
解题思路:
方法一:一次遍历
Golang
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*/
func deleteDuplicates(head *ListNode) *ListNode {if head == nil {return nil}// new headnewHead := &ListNode{Next: head,}cur := newHeadfor cur.Next != nil && cur.Next.Next != nil {if cur.Next.Val == cur.Next.Next.Val {x := cur.Next.Val// 删除所有值等于x的节点。// 一直持续到找到一个值不等于x的节点或者链表结束。for cur.Next != nil && cur.Next.Val == x {cur.Next = cur.Next.Next}continue}cur = cur.Next}return newHead.Next
}
C++
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if (!head) {return head;}ListNode* dummy = new ListNode(0, head);ListNode* cur = dummy;while (cur->next && cur->next->next) {if (cur->next->val == cur->next->next->val) {int x = cur->next->val;while (cur->next && cur->next->val == x) {cur->next = cur->next->next;}}else {cur = cur->next;}}return dummy->next;}
};
Java
class Solution {public ListNode deleteDuplicates(ListNode head) {if (head == null) {return head;}ListNode dummy = new ListNode(0, head);ListNode cur = dummy;while (cur.next != null && cur.next.next != null) {if (cur.next.val == cur.next.next.val) {int x = cur.next.val;while (cur.next != null && cur.next.val == x) {cur.next = cur.next.next;}} else {cur = cur.next;}}return dummy.next;}
}
复杂度分析
时间复杂度: O ( n ) O(n) O(n)。
空间复杂度: O(1) 。