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

题目描述

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

思路：直接处理

 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         ListNode *res = new ListNode(0), *tmp = res;
15         ListNode *cur = pHead, *last;
16         bool flag = false; //判断一个元素是否重复
17         //从表头开始
18         while (cur != NULL) {
19             last = cur->next;
20             flag = false;
21             while ((last != NULL) && (cur->val == last->val)) {
22                 last = last->next;
23                 flag = true;
24             }
25             //如果有重复，那么cur指向下一个第一次不重复的节点
26             if (flag) {
27                 cur = last;
28             } else {
29                 tmp->next = cur;
30                 tmp = cur;
31                 //tmp->next = NULL; 千万注意不要在这里断掉，cur->next就会被置为NULL
32                 cur = cur->next;
33                 tmp->next = NULL;
34             }
35         }
36         return res->next;
37     }
38 };

以上代码内存未回收，更新版本如下：

 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 
13     ListNode* deleteDuplication(ListNode* pHead)
14     {
15         ListNode *res = new ListNode(0), *tmp = res; //res为表头，为方便链表一个节点重复的情况
16         ListNode *cur = pHead, *last = nullptr, *pNode; //pNode指向要回收的节点
17         bool flag = false; //判断某一个节点是否重复
18         while (cur != nullptr) {
19             flag = false;
20             last = cur->next;
21             while (last != nullptr && cur->val == last->val) {
22                 pNode = last;
23                 last = last->next;
24                 
25                 delete pNode;
26                 pNode = nullptr;
27                 
28                 flag = true;
29             }
30             //如果有重复，那么cur指向下一个第一次不重复的节点
31             if (flag) {
32                 pNode = cur;
33                 cur = last;
34                 
35                 delete pNode;
36                 pNode = nullptr;
37                 
38             } else {
39                 tmp->next = cur;
40                 tmp = cur;
41                 //tmp->next = NULL; 千万注意不要在这里断掉，cur->next就会被置为NULL
42                 cur = cur->next;
43                 tmp->next = nullptr;
44             }
45         }
46         return res->next;
47     }
48 }；

递归解法

 1 class Solution {
 2 public:
 3     ListNode* deleteDuplication(ListNode* pHead)
 4     {
 5         if (pHead == NULL)
 6             return NULL;
 7         if (pHead != NULL && pHead->next == NULL)
 8             return pHead;
 9         ListNode *cur = pHead->next;
10         if (cur->val == pHead->val) {
11             cur = cur->next;
12             while (cur && cur->val == pHead->val) {
13                 cur = cur->next;
14             }
15             return deleteDuplication(cur);
16         } else {
17             pHead->next = deleteDuplication(cur);
18             return pHead;
19         }
20     }
21 };

更新版本如下：

 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) {
15             return nullptr;
16         }
17         if (pHead != nullptr && pHead->next == nullptr) {
18             return pHead;
19         }
20         ListNode *cur = pHead->next;
21         if (cur->val == pHead->val) {
22             ListNode *tmp = cur;
23             cur = cur->next;
24             delete tmp;
25             tmp = nullptr;
26             while (cur != nullptr && cur->val == pHead->val) {
27                 ListNode *tmp = cur;
28                 cur = cur->next;
29                 delete tmp;
30                 tmp = nullptr;
31             }
32             return deleteDuplication(cur);
33         } else {
34             pHead->next = deleteDuplication(cur);
35             return pHead;
36         }
37     } 
38 };