题目描述
题目链接: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.
解题思路
由于链表已经经过排序,所以只需要在每一个节点后面遍历,将遇到的第一个值不相等的节点作为下一个节点连接即可,代码如下:
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