Remove Duplicates from Sorted List II
Remove Duplicates from Sorted List II
https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Thoughts
因为head可能被删掉,因此需要dummy
对重复中的第一个的删除,判断条件是它和它后面的值是否相等。
对重复中的最后一个的删除,需要判断它和上个被删的值是否相等,因此还需要个prior
.
删除后相当于节点自动前移,不需要node = node.next; 反之则需要。
Code
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode d_head(-1);
ListNode *d = &d_head, *node = d, *prior = NULL;
d->next = head;
while (node != NULL && node->next != NULL) {
auto next = node->next;
if (prior != NULL && next->val == prior->val || next->next != NULL && next->next->val == next->val) {
node->next = next->next;
} else {
node = next;
}
prior = next;
}
return d->next;
}
};
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode node = head;
ListNode prior = dummy;
int delVal = 0; boolean valid = false;
while (node != null) {
if (node.next != null && node.val == node.next.val || node.val == delVal && valid) {
prior.next = node.next;
delVal = node.val;
valid = true;
} else {
prior = node;
}
node = node.next;
}
return dummy.next;
}
}
Analysis
TC: O(n)
Last updated
Was this helpful?