在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5

时间:2022-07-25 09:54:04

// test20.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<string.h>
#include<deque>
#include <forward_list> using namespace std; struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
}; class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if (pHead == NULL) return NULL; ListNode* copyHead = selectNoRepeatNode(pHead); //第一个不重复的节点
ListNode* cur= copyHead;
while (cur!=NULL) //反复调用查找不重复节点的方法
{
cur->next = selectNoRepeatNode(cur->next);
cur = cur->next;
} return copyHead;
} ListNode* selectNoRepeatNode(ListNode* pHead) //查找不重复节点的方法
{
if (pHead == NULL) return NULL;
ListNode* pre = NULL;
ListNode* cur = pHead;
ListNode* post = pHead->next; while (cur != NULL)
{
if (pre == NULL && post == NULL)//就cur这一个节点
{
// copyHead = cur;
break;
}
else if (pre == NULL &&post != NULL && cur->val != post->val) //只有post节点
{
break;
}
else if (pre != NULL && post == NULL && cur->val != pre->val)//只有前置节点
{
break;
}
else if(pre != NULL && post != NULL &&pre->val != cur->val&& post->val != cur->val )//pre和post都不为空
{ break;
}
pre = cur; //此处不要忘了更新pre cur 和post,只更新cur是不行的
cur = cur->next;
post = cur->next;
} return cur;
} };
int main()
{ //vector<int> vec = { 49,38,65,97,76,13,27,49};
Solution so;
//ListNode node1(1);
//ListNode node2(2);
//ListNode node3(3);
//ListNode node4(3);
//ListNode node5(4);
//ListNode node6(4);
//ListNode node7(5); ListNode node1(1);
ListNode node2(2);
ListNode node3(1);
ListNode node4(2);
ListNode node5(2);
ListNode node6(3);
ListNode node7(4); ListNode* node01 = &node1;
ListNode* node02 = &node2;
ListNode* node03 = &node3;
ListNode* node04 = &node4;
ListNode* node05 = &node5;
ListNode* node06 = &node6;
ListNode* node07 = &node7; node01->next = node02;
node02->next = node03;
node03->next = node04;
node04->next = node05;
node05->next = node06;
node06->next = node07; //ListNode* ls = so.selectNoRepeatNode(node01);
ListNode* ls =so.deleteDuplication(node01);
// cout << "入口节点是:" << so.EntryNodeOfLoop(node01)->val << endl;
// so.print();
//输出ListNode
//while (node01 != NULL)
//{
// cout << node01->val << " ";
// node01 = node01->next;
//}
while (ls != NULL)
{
cout << ls->val << " ";
ls = ls->next;
} return 0;
}