剑指offer56:删除链表中重复的结点,排序的链表中,删除重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
程序员文章站
2022-03-25 22:03:27
1 题目描述 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5 2 思路和方法 (1)链表为空,不必多说,return NULL; (2)如果恰恰是头结点与头结点的后一个重复了 ......
1 题目描述
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
2 思路和方法
(1)链表为空,不必多说,return null
;
(2)如果恰恰是头结点与头结点的后一个重复了,这种情况是可以发生的,那头结点就要被删除,另选新的结点作为头结点。如何处理这种特殊情况,多申请一个指针就可以了。
3 c++核心代码
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(null == phead) return null; 15 listnode* pre = null, *cur = phead; 16 while(null != cur){ 17 if(null != cur->next && cur->val == cur->next->val){ //凡是涉及解引用,就要判空,这是职业素养!!! 18 int repeat = cur->val; 19 listnode* pnext; 20 while(null != cur && cur->val == repeat){ //通过循环删除所有值为repeat的结点 21 pnext = cur->next; 22 delete cur; 23 cur = pnext; 24 } 25 }else{ 26 pre = cur; //pre指向不重复的结点 27 cur = cur->next; 28 } 29 30 if(null == pre){ 31 phead = cur; 32 }else{ 33 pre->next = cur; 34 } 35 } 36 return phead; 37 } 38 };
参考资料
https://blog.csdn.net/qq_41822235/article/details/82832898
上一篇: Django 实现登录后跳转