Description
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
Example 1:
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
Example 2:
Input: head = [1,1,1,2,3]
Output: [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.
解题
方法一
思路
快慢指针，
- 遇到相同的快指针（curr）不断往后移
- 慢指针（prev）发现自己后面指的节点不是当初的那个节点（说明有重复节点，需要删除），直接把链接连到快指针后面，如果还是当初连的那个快节点的话，就保留当前节点，再进一步
- 快指针往后继续移
代码
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode prev = dummy, curr = head;
prev.next = head;
while (curr != null) {
while (curr.next != null && curr.val == curr.next.val) {
curr = curr.next;
}
if (prev.next != curr) {
prev.next = curr.next;
} else {
prev = prev.next;
}
curr = curr.next;
}
return dummy.next;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *prev = dummy;
while (prev->next) {
ListNode *curr = prev->next->next;
while (curr && prev->next->val == curr->val) {
curr = curr->next;
}
if (prev->next->next == curr) {
prev = prev->next;
} else {
prev->next = curr;
}
}
return dummy->next;
}
};
复杂度分析
- 时间复杂度: O(n)
- 空间复杂度: O(1)
Top comments (0)