首页 > 代码库 > Leetcode | Remove Duplicates from Sorted List I && II

Leetcode | Remove Duplicates from Sorted List I && II

2024-07-04 20:13:03   222人阅读

Remove Duplicates from Sorted List I

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

如果下一个节点和当前节点的值一样，就继续往后。这样找到的是重复数的最后一个。比如1->1->2; 

当然也可以找到重复数的第一个数；

注意delete掉那些重复的点。

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

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

和Remove Duplicates from Sorted List I类似。加了一个判断是否重复数的条件。最后tail要指向NULL，因为原链表最后一个元素不一定会加进来。

这道题用c++很奇怪。下面的代码没有delete是可以accepted的。

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

但是加了delete的逻辑之后就runtime error了。这份代码应该是没有问题的。难道是leetcode自己有问题？

 1 class Solution {
 2 public:
 3     ListNode *deleteDuplicates(ListNode *head) {
 4         ListNode *p = head, *newH = NULL, *tail, *current, *tmp;
 5         while (p != NULL) {
 6             current = p;
 7             while (p->next != NULL && p->next->val == p->val) {
 8                 tmp = p->next; 
 9                 delete p;
10                 p = tmp;
11             }
12             tmp = p->next;
13             if (p == current) {
14                 if (newH == NULL) {
15                     newH = p;
16                 } else {
17                     tail->next = p; 
18                 }
19                 tail = p;
20             } else {
21                 delete p;
22             }
23             p = tmp;
24         }
25         if (tail) tail->next = NULL;
26         return newH;
27     }
28 };

 


联系
我们