剑指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         else
17         {
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                 else
39                 {
40                     pre = cur;
41                     cur = cur->next;
42                 }
43                 nex = nex->next;
44             }
45             return newhead->next;
46         }
47     }
48 };

 

上一篇:第十五章 例行性工作(crontab)--循环执行的例行性工作调度 crontab(定时任务)


下一篇:92. 反转链表 II.反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。