剑指offer：删除链表中重复的结点

题目描述：

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

思路分析：

要考虑两种情况，链表中结点为0或1，此时直接返回原链表；第二种情况就是链表中包含两个及以上的结点。

解决第一种情况直接进行一个判断即可，第二种情况，需要定义三个指针pre, cur, nex来解决。其中为了最终返回链表头指针，需要额外定义一个指针，指向链表头。这里定义这个指针为newhead，newhead的next为给定链表的头。接下来令pre指向newhead，cur指向pHead，nex指向pHead->next。接下来进行判断，当cur->val==nex->val时，继续向后循环遍历，直到nex->val大于cur->val，此时pre->next=nex；当cur->val<nex->val时，即满足条件，向后继续遍历，那么pre=cur, cur=cur->next。

代码：

 /*

 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(-);

             newhead->next = pHead;

             ListNode* pre=newhead;

             ListNode* cur=pHead;

             ListNode* nex=pHead->next;

             while(cur!=nullptr && cur->next!=nullptr)

             {

                 if(cur->val==nex->val)

                 {

                     while(nex!=nullptr && cur->val==nex->val)

                     {

                         ListNode* tmp = nex;

                         nex = nex->next;

                         delete tmp;

                         tmp = nullptr;

                     }

                     pre->next = nex;

                     cur = nex;

                 }

                 else

                 {

                     pre = cur;

                     cur = cur->next;

                 }

                 nex = nex->next;

             }

             return newhead->next;

         }

     }

 };

巴特西

剑指offer：删除链表中重复的结点

最新文章

热门文章