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

剑指offer:删除链表中重复的结点
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码 

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说剑指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。

 

代码:

 1 /* 2 struct ListNode { 3  int val; 4  struct ListNode *next; 5  ListNode(int x) : 6  val(x), next(NULL) { 7  } 8 }; 9 */10 class Solution {11 public:12 ListNode* deleteDuplication(ListNode* pHead)13  {14 if(pHead==nullptr || pHead->next==nullptr)15 return pHead;16 else17  {18 ListNode* newhead = new ListNode(-1);19 newhead->next = pHead;20 ListNode* pre=newhead;21 ListNode* cur=pHead;22 ListNode* nex=pHead->next;23 while(cur!=nullptr && cur->next!=nullptr)24  {25 if(cur->val==nex->val)26  {27 while(nex!=nullptr && cur->val==nex->val)28  {29 ListNode* tmp = nex;30 nex = nex->next;31 32 delete tmp;33 tmp = nullptr;34  }35 pre->next = nex;36 cur = nex;37  }38 else39  {40 pre = cur;41 cur = cur->next;42  }43 nex = nex->next;44  }45 return newhead->next;46  }47  }48 };

 

转载于:https://www.cnblogs.com/LJ-LJ/p/11066936.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29744

发表评论