解题思路:好难啊!勉强听懂;)
添加一个虚拟头结点 dummy,将其 next 指针指向原链表的头结点 head,用于处理头结点重复的情况。
定义指针 p 指向虚拟头结点 dummy,用于遍历链表。
进入循环,当 p 的 next 指针不为空时.定义指针 q 指向 p 的 next,用于查找重复节点。
再进入循环,当 q 的 next 指针不为空且 q 的值与 q 的 next 的值相等时,将 q 移动到下一个节点 q->next,直到 q 的值与 q 的 next 的值不相等为止,找到一段重复节点。
如果 q 指向了 p 的 next,即中间没有隔开,说明没有重复的数字,则将 q 赋值给 p,继续下一个节点的判断。
否则,即存在重复的节点,将 p 的 next 指针指向 q->next,即跳过重复的节点。
当循环结束后,虚拟头结点 dummy 的 next 指针指向的链表即为删除重复节点后的链表。
返回虚拟头结点 dummy->next,得到删除重复节点后的链表。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* head) {
ListNode*dummy=new ListNode(-1);//虚拟头结点
dummy->next=head;
ListNode*p=dummy;
while(p->next)//当p的next指针不为空时
{
ListNode*q=p->next;
while(q->next&&q->next->val==p->next->val)q=q->next;//当q的next不为空且两数重复时,q往后走
if(q==p->next)p=q;//中间没隔,紧贴着,说明没有重复的数字,则将q赋给p
else p->next=q->next;//若有重复的则将q的next赋给p的next,新链条将跳过重复部分。继续检查有无重复。
}
return dummy->next;//最后返回虚拟头结点的next,得到一串新链表。
}
};