删除链表中重复的节点
这是剑指offer中 18题的第二小题。
第一小题:删除链表中指定节点
需要考虑当该节点在链表的结尾、该节点在链表的头节点、当链表在中间节点的三种情况,
这是删除链表的相同节点
这道题需要注意的是:
1、可能链表的头节点被删除的情况
2、可以参照链表的反转思路,使用三个指针来实现
以下是代码
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* deleteDuplication(ListNode* pHead) { if(pHead == nullptr && pHead->next == nullptr) { return pHead; }else { ListNode *newHead = new ListNode(0); newHead->next = pHead; //定义三个节点,一个指向当前节点、当前节点的前一个节点、当前节点的后一个节点 ListNode *PerNode = nullptr; ListNode *p = pHead;//当前节点,也是遍历的开始 ListNode *next = nullptr;//当前节点的下一个节点 while(p!=nullptr && p->next != nullptr) { //先保存当前节点的指向 next = p->next; if(p->val == next->val)//当出现重复节点的时候 { while(next != nullptr && next->val == p->val) { //循环主要是为了继续向后搜寻节点相等的部分 next = next->next; } //将pre直接指向next就相当于删除了当前节点 PerNode->next = next; p = next; }else{ //当前节点和下一个节点值不相等,就继续移动指针 PerNode = p; p = p->next; } } return newHead->next; } } };