设计一个算法,在非递减有序的带头结点的单链表中删除值相同的多余结点。
时间: 2023-04-22 10:00:37 浏览: 133
试设计实现在单链表中删去值相同的多余结点的算法。
算法步骤如下:
1. 定义两个指针p和q,p指向头结点,q指向第一个非头结点。
2. 循环遍历链表,如果p的值等于q的值,则删除q结点,否则p和q同时后移一个结点。
3. 循环结束后,返回头结点即可。
代码实现如下:
```
ListNode* deleteDuplicates(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* p = head;
ListNode* q = head->next;
while (q != nullptr) {
if (p->val == q->val) {
p->next = q->next;
delete q;
q = p->next;
} else {
p = p->next;
q = q->next;
}
}
return head;
}
```
阅读全文