82. Remove Duplicates from Sorted List II【Medium】
2024-08-31 05:32:36
82. Remove Duplicates from Sorted List II【Medium】
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
解法一：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
} ListNode * dummy = new ListNode(INT_MIN);
dummy->next = head;
head = dummy;
int duplicate; while (head->next != NULL && head->next->next != NULL) {
if (head->next->val == head->next->next->val) {
duplicate = head->next->val;
while (head->next != NULL && head->next->val == duplicate) {
ListNode * temp = head->next;
free(temp);
head->next = head->next->next;
}
}
else {
head = head->next;
}
}
return dummy->next; }
};
nc
解法二：
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head) return head;
ListNode dummy();
dummy.next = head;
ListNode *pre = &dummy;
ListNode *cur = head;
while(cur && cur->next){
while(cur->next && cur->val == cur->next->val) cur = cur->next;
if(pre->next == cur){
pre = cur;
cur = cur->next;
} else {
cur = cur->next;
pre->next = cur;
}
}
return dummy.next;
}
};
参考了@liismn 的代码
解法三：
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head||!head->next) return head;
ListNode* dummy = new ListNode();
ListNode* tail = dummy;
int flag = true; // should the current head be added ?
while(head){
while(head&&head->next&&head->val==head->next->val)
{
flag = false; // finds duplicate, set it to false
head = head->next;
}
if(flag) // if should be added
{
tail->next = head;
tail = tail->next;
}
head = head->next;
flag = true; // time for a new head value, set flag back to true
}
tail->next = nullptr; // Don't forget this... I did..
return dummy->next;
}
};
参考了@GoGoDong 的代码
解法四：
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
if (head.next != null && head.val == head.next.val) {
while (head.next != null && head.val == head.next.val) {
head = head.next;
}
return deleteDuplicates(head.next);
} else {
head.next = deleteDuplicates(head.next);
}
return head;
}
递归，参考了@totalheap 的代码，还不太明白
最新文章
- Spring mvc
- 参数化命令相关知识点之==================防止SQl的注入
- 遍历Map
- ExtJs文件上传(Ext.ux.form.FileUploadField)
- Codeforces Round #382 (Div. 2)B. Urbanization 贪心
- Spring Autowiring by AutoDetect
- HDU 1562 Guess the number
- 学习笔记：javascript 文档对象（document）
- TCP/IP协议全解析 三次握手与四次挥手［转］
- Hive-ORC文件存储格式（续）
- tomcat自动运行磁盘任意位置上的项目、使用Maven对tomcat进行自动部署
- Netty、t-io、Voovan 框架比较
- macos + vs code + grep 进行多文件搜索
- ASP.NET C# 实现实时用户在线
- 剑指Spring源码（一）
- sqoop的安装
- PHP+Ajax实现文件上传功能
- noip第27课资料
- 使用linux的shell脚本实现在当前行重复动态显示时间等字符串信息（不另起新行）
- Unity3d资源管理分析