数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中从已排序的链表中删除重复项
假设我们有一个已排序的链表；我们必须删除所有重复项，使每个元素只出现一次。
因此，如果输入类似于 [1,1,2,3,3,3,4,5,5]，则输出将是 [1,2,3,4,5]
要解决这个问题，我们将遵循以下步骤 −
dummy := 创建一个新节点，其值为 -inf
dummy 的下一项 := head
curr = dummy
当 curr 非零时，执行 −
next = curr 的下一项
当 (next 不为 null 且 next 的值为 same as curr 的值) 时，执行 −
next := next 的下一项
curr 的下一项 := next
curr := next
返回 dummy 的下一项
示例
让我们看看以下实现，以获得更好的理解 −
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
void print_list(ListNode *head){
ListNode *ptr = head;
cout << "[";
while(ptr){
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << "]" << endl;
}
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode*dummy = new ListNode(INT_MIN);
dummy->next = head;
ListNode * curr = dummy;
while(curr){
ListNode * next = curr->next;
while(next && next->val==curr->val)
next = next->next;
curr->next = next;
curr=next;
}
return dummy->next;
}
};
main(){
Solution ob;
vector<int> v = {1,1,2,3,3,3,4,5,5};
ListNode *head = make_list(v);
print_list(ob.deleteDuplicates(head));
}输入
{1,1,2,3,3,3,4,5,5}输出
[1, 2, 3, 4, 5, ]
更新于：2020 年 6 月 10 日
1K+ 浏览量
Advertisements