题目描述
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
思路
- 如果链表为空,或者只有一个结点,直接返回
- 如果链表结点大于等于2,则比较当前结点和下一个结点是否相同,如果相同,则删除当前结点和下一个结点,比较下下个结点是否和当前结点相同,如果相同继续删除,直至与当前结点不同。
- 返回链表表头是第一个不重复结点,需要一个前驱结点prenode记录不重复链表,其next应该初始为NULL,如果有下一个不重复结点,则next是下一个不重复结点。
- 测试用例:
a. 空
b. 一个结点
c. 两个重复结点
d. 1->1->2->3
e. 1->2->3->3->4->4
具体见code
code
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
ListNode* phead=NULL;
if(pHead==nullptr)
return phead;
ListNode* pnode=pHead;
ListNode *prenode=NULL;
bool tobedelete=false;
while(pnode)
{
ListNode* pnext=pnode->next;
tobedelete=false;
if(pnext&&pnext->val==pnode->val)
{
tobedelete=true;
}else{
if(phead==NULL)
{
phead=pnode;
prenode=phead;
}
else {
prenode->next=pnode;
prenode=pnode;
prenode->next=NULL;
}
pnode=pnext;
}
if(tobedelete)
{
int val=pnode->val;
ListNode* pdelete=NULL;
while(pnode&&pnode->val==val)
{
pdelete=pnode;
pnode=pdelete->next;
delete pdelete;
pdelete=NULL;
}
}
}
return phead;
}
};
code注意事项
- 注意链表结点删除,需要赋值为NULL
- 不重复链表最后一个结点next初始值应该是NULL,即1->2->2->4->5->5这种情况下,如果非NULL,则会最后两个野指针,出错。