0%

[Leetcode]83. Remove Duplicates from Sorted List(C++)

题目描述

题目链接:83. Remove Duplicates from Sorted List

例子

例子 1

Input: head = [1,1,2]
Output: [1,2]

例子 2

Input: head = [1,1,2,3,3]
Output: [1,2,3]

Constraints

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.

解题思路

由于链表已经经过排序,所以只需要在每一个节点后面遍历,将遇到的第一个值不相等的节点作为下一个节点连接即可,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* curr = head;
ListNode* prev = head;
while (curr) {
while (curr && curr->val == prev->val) curr = curr->next;
prev->next = curr;
prev = curr;
}

return head;
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 83.RemoveDuplicatesFromSortedList.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions