剑指offer-删除链表中重复的节点

时间：2023-03-09 03:02:48
剑指offer-删除链表中重复的节点

题目描述

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

解题思路

定义preNode指向当前结点pNode的前一个节点，每次访问pNode时首先判断它与后面节点是否重复，若重复则置bool型变量needDel为true。不需要删除时preNode和pNode分别指向下一个节点；需要删除时，首先保存pNode指向的结点值，依次向后遍历并删除每一个重复节点，直到找到第一个不重复的节点用pNext指向它。然后判断preNode是否为NULL，若为空说明当前重复节点是从首节点开始的，则直接把头指针pHead指向pNext；若不为空，则用preNode的next指针指向pNext。最后把当前结点pNode指向pNext即可。

代码

 /*

 struct ListNode {

     int val;

     struct ListNode *next;

     ListNode(int x) :

         val(x), next(NULL) {

     }

 };

 */

 class Solution {

 public:

     ListNode* deleteDuplication(ListNode* pHead)

     {

         ListNode* preNode = NULL;

         ListNode* pNode = pHead;

         while(pNode){

             ListNode* pNext = pNode->next;

             bool needDel = false;

             if(pNext&&pNext->val == pNode->val)

                 needDel = true;

             if(!needDel){

                 preNode = pNode;

                 pNode = pNode->next;

             }

             else{

                 int val = pNode->val;

                 ListNode* pDel = pNode;

                 while(pDel&&pDel->val == val){

                     pNext = pDel->next;

                     delete pDel;

                     pDel = pNext;

                 }

                 if(preNode == NULL)

                     pHead = pNext;

                 else

                     preNode->next = pNext;

                 pNode = pNext;

             }

         }

         return pHead;

     }

 };

相关文章