NC278. 删除链表中重复的结点
描述
示例1
输入:
{1,2,3,3,4,4,5}
输出:
{1,2,5}
示例2
输入:
{1,1,1,8}
输出:
{8}
C 解法, 执行用时: 2ms, 内存消耗: 412KB, 提交时间: 2021-11-22
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @return ListNode类
*/
struct ListNode* deleteDuplication(struct ListNode* pHead ) {
// write code here
if(pHead == NULL ||pHead->next == NULL){
return pHead;
}
if(pHead->val != pHead->next->val){
//不是重复节点，返回给调用者的 pHead->next
pHead->next = deleteDuplication(pHead->next);
return pHead;
}else{
struct ListNode* temp = pHead;
// 跳过值与当前结点相同的全部结点,找到第一个与当前结点不同的结点
while(temp != NULL && pHead->val == temp->val){
temp = temp->next;
}
return deleteDuplication(temp);
}
}
C++ 解法, 执行用时: 2ms, 内存消耗: 544KB, 提交时间: 2022-02-09
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
/*
题目的主要信息：
1. 在一个非降序的链表中，存在重复的结点，删除该链表中重复的结点，重复的结点不保留
2. 进阶要求：时间复杂度：O(n)，空间复杂度：O(n)
方法一：哈希表
具体做法：
1. 可以遍历一次链表用哈希表记录每个结点值出现的次数，然后在链表前加一个结点值为0的表头（返回的时候，
直接返回dummy->next，加表头是为了防止删除时全部结点删完了）。
2. 再次遍历该链表，对于每个结点值检查哈希表中的计数，只留下计数为1的，其他情况都删除。
复杂度分析：
时间复杂度：O(n)，其中n为链表结点数，一共两次遍历，unordered_map每次计数、每次查询都是O(1)
空间复杂度：O(n)，最坏情况下n个结点都不相同，哈希表长度为n
*/
ListNode* deleteDuplication1(ListNode* pHead) {
if(pHead == NULL) //空链表
return NULL;
unordered_map<int, int> mp;
ListNode* cur = pHead;
while(cur != NULL){ //遍历链表统计每个结点值出现的次数
mp[cur->val]++;
cur = cur->next;
}
ListNode* dummy = new ListNode(0);
dummy->next = pHead; //在链表前加一个表头
cur = dummy;
while(cur->next != NULL){ //再次遍历链表
if(mp[cur->next->val] != 1) //如果结点值计数不为1
cur->next = cur->next->next; //删去该结点
else
cur = cur->next;
}
return dummy->next; //去掉表头
}
/*
方法二：直接比较删除
具体做法：
1. 其实在遍历链表的时候也可以直接删除，因为这是一个升序链表，重复的结点都连在一起。
2. 同样给链表前加上表头，然后遍历，如果遇到了两个相邻结点相同，
则新开内循环将这一段所有的相同都遍历过去，第一个相同前的结点直接连上第一个不相同值的结点。
3. 返回时依然要去掉表头。
复杂度分析：
时间复杂度：O(n)，其中n为链表结点数，只有一次遍历
空间复杂度：O(1)，只开辟了临时指针，没有额外空间
*/
ListNode* deleteDuplication(ListNode* pHead) {
if(pHead == NULL) //空链表
return NULL;
ListNode* dummy = new ListNode(0);
dummy->next = pHead; //在链表前加一个表头
ListNode* cur = dummy;
while(cur->next != NULL && cur->next->next != NULL){
if(cur->next->val == cur->next->next->val){ //遇到相邻两个结点值相同
int temp = cur->next->val;
while (cur->next != NULL && cur->next->val == temp) //将所有相同的都跳过
cur->next = cur->next->next;
}
else
cur = cur->next;
}
return dummy->next; //返回时去掉表头
}
};
/************************** 下方为之前提交的代码 *****************************/
class Solution2 {
public:
// 暴力解法：使用set
// 根据题意，显然如果能够知道重复的值是什么，然后再遍历一次单链表，删除重复值即可。
// 找重复值的具体步骤：
// 1. 初始化：set<int> st
// 2. 遍历单链表相邻两个元素，如果相等，就加入到set当中
// 3. 直到单链表遍历完
// 删除重复值的具体步骤：
// 1. 初始化：pre指针指向重复值的前一个节点，cur指向当前遍历的节点值
// 2. 遍历单链表当前元素，然后再set中检查，如果是重复值，就删除，pre->next = cur->next
// 3. 否则，不是重复值，pre = pre->next, cur = cur->next
// 4. 直到单链表遍历完
// 时间复杂度：O(2n),遍历了2次单链表
// 空间复杂度：最坏O(n), 最好O(1)
ListNode* deleteDuplication(ListNode* pHead)
{
if (!pHead) return pHead;
set<int> st;
ListNode *pre = pHead;
ListNode *cur = pHead->next;
while (cur) {
if (pre->val == cur->val) {
st.insert(pre->val);
}
pre = pre->next;
cur = cur->next;
}
ListNode *vhead = new ListNode(-1);
vhead->next = pHead;
pre = vhead;
cur = pHead;
while (cur) {
if (st.count(cur->val)) {
cur = cur->next; //缓存当前节点的下一节点
pre->next = cur; //删除重复节点
} else {
pre = pre->next;
cur = cur->next;
}
}
return vhead->next;
}
// 非递归解法：直接删除法 - 更容易理解
// 常规思路：利用3个指针
// 时间复杂度：O(n)；空间复杂度：O(1)
ListNode* deleteDuplication1(ListNode* pHead)
{
ListNode *newHead = new ListNode(-1);
newHead->next = pHead;
ListNode *pre = newHead, *cur = pHead;
while (cur) {
if (cur->next && cur->val == cur->next->val) {
cur = cur->next;
while (cur->next && cur->val == cur->next->val) {
cur = cur->next;
} //循环的目的是为了遍历连续重复值，循环结束后cur指向当前批重复集合的最后一个重复元素
cur = cur->next; // 先把当前节点指向重复元素的下一元素
pre->next = cur; // 删除当前批次的重复元素
} else {
pre = cur;
cur = cur->next;
}
}
return newHead->next;
}
// 相同思路：利用4个指针 - 也容易理解
// 优化点：在遍历单链表的时候，检查当前节点与下一点是否为相同值，
// 如果相同，继续查找相同值的最大长度，然后指针改变指向。
ListNode* deleteDuplication2(ListNode* pHead)
{
if(pHead==NULL||pHead->next==NULL) return pHead;
else {
//新建一个节点，防止头结点要被删除
ListNode* newHead=new ListNode(-1);
newHead->next=pHead;
ListNode* pre=newHead;
ListNode* cur=pHead;
ListNode* next=NULL;
while(cur!=NULL && cur->next!=NULL)
{
next=cur->next;
if(cur->val==next->val)//如果当前节点的值和下一个节点的值相等
{
while(next!=NULL && next->val==cur->val)//向后重复查找
next=next->next; //退出循环时next会指向重复元素的下一元素
pre->next=next;//指针赋值，就相当于删除
cur=next; //将当前节点指针cur指向next
}
else//如果当前节点和下一个节点值不等，则向后移动一位
{
pre=cur;
cur=cur->next;
}
}
return newHead->next;//返回头结点的下一个节点
}
}
//递归解法 - 难以理解！
ListNode* deleteDuplication3(ListNode* pHead) {
if (pHead==NULL)
return NULL;
if (pHead!=NULL && pHead->next==NULL)
return pHead;
ListNode* current;
if (pHead->next->val==pHead->val){
current=pHead->next->next;
while (current != NULL && current->val==pHead->val)
current=current->next;
return deleteDuplication(current);
}
else {
current=pHead->next;
pHead->next=deleteDuplication(current);
return pHead;
}
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 544KB, 提交时间: 2021-11-18
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead) {
ListNode *vhead = new ListNode(-1);
vhead->next = pHead;
ListNode *pre = vhead, *cur = pHead;
while (cur) {
if (cur->next && cur->val == cur->next->val) {
cur = cur->next;
while (cur->next && cur->val == cur->next->val) {
cur = cur->next;
}
cur = cur->next;
pre->next = cur;
}
else {
pre = cur;
cur = cur->next;
}
}
return vhead->next;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 548KB, 提交时间: 2022-02-09
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead) {
// 哨兵节点
ListNode *pre, *vhead = new ListNode(-1);
// 哨兵节点next节点初始化为链表头
pre = vhead;
vhead->next = pHead;
while (pHead)
{
// 如果当前节点与其next节点相同
if (pHead->next && pHead->val == pHead->next->val)
{
// 节点向后移动
pHead = pHead->next;
// 一直移动到当前相同节点的最后一个节点
while (pHead->next && pHead->val == pHead->next->val)
{
pHead = pHead->next;
}
// 跳过最后一个相等的节点，到不相同节点上
pHead = pHead->next;
// 处理前面节点
pre->next = pHead;
}
else
{
// 如果当前节点和后面节点不同
pre = pHead;
pHead = pHead->next;
}
}
return vhead->next;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 576KB, 提交时间: 2021-11-17
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead) {
if(pHead==nullptr)
return pHead;
if(pHead->next==nullptr)
return pHead;
ListNode *p=pHead,*p0;
do{
while(p->val==p->next->val){
p=p->next;
if(p->next==nullptr)
return nullptr;
}
if(p!=pHead){
pHead=p->next;
}
if(pHead==nullptr)
return pHead;
p=pHead;
if(p->next==nullptr)
break;
}while(p->val==p->next->val);
while(p->next!=nullptr){
if(p->next->next==nullptr)
break;
if(p->next->val==p->next->next->val){
p0=p->next->next;
if(p0->next!=nullptr){
while(p0->val==p0->next->val){
p0=p0->next;
}
}
p->next=p0->next;
}
else p=p->next;
}
return pHead;
}
};