Remove Duplicates from Sorted List I&&II

Remove Duplicates from Sorted List
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 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *deleteDuplicates(ListNode *head) {
12         if( !head ) return 0;
13         ListNode* pre = head;   //  
14         ListNode* cur = pre->next;  //  
15         while( cur ) {
16             if( cur->val == pre->val ) {    //      ，    
17                 ListNode* p = cur;
18                 cur = cur->next;
19                 pre->next = cur;
20                 delete p;
21             } else {    //      
22                 cur = cur->next;
23                 pre = pre->next;
24             }
25         }
26         return head;
27     }
28 };

Remove Duplicates from Sorted List II  
Total Accepted: 21273 Total Submissions: 85697My Submissions
 
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 .
重複するデータはすべて削除しなければならなくて、タグを設けることができて、もし重複するノードがあることを発見したら、その値をタグに与えて、それからタグの値に出会ったノードは直接削除します

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *deleteDuplicates(ListNode *head) {
12         if( !head ) return 0;
13         const int INF = 0x3fffffff; //       
14         ListNode node(-1);  //     ，    
15         node.next = head;
16         ListNode* pre = &node;
17         ListNode* cur = head;
18         int needDelete = INF;   //      
19         while( cur ) {
20             if( cur->val == needDelete ) {  //        ，      
21                 ListNode* p = cur;
22                 cur = cur->next;
23                 pre->next = cur;
24                 delete p;
25             } else if( cur->next && cur->val == cur->next->val ) {  //        ，          
26                 needDelete = cur->val;
27             } else {    //    
28                 cur = cur->next;
29                 pre = pre->next;
30             }
31         }
32         return node.next;
33     }
34 };

ここの不可能値は、可能であれば論理的に判断する必要があります.そうしないと、大きなバグが発生します.特に面接官が尋ねると

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *deleteDuplicates(ListNode *head) {
12         if( !head ) return 0;
13         ListNode node(-1);  //     ，    
14         node.next = head;
15         ListNode* pre = &node;
16         ListNode* cur = head;
17         while( cur && cur->next && cur->val != cur->next->val ) {
18             pre = cur;
19             cur = cur->next;
20         }
21         if( !cur->next ) return node.next;
22         int needDelete = cur->val;
23         while( cur ) {
24             if( cur->val == needDelete ) {  //        ，      
25                 ListNode* p = cur;
26                 cur = cur->next;
27                 pre->next = cur;
28                 delete p;
29             } else if( cur->next && cur->val == cur->next->val ) {  //        ，          
30                 needDelete = cur->val;
31             } else {    //    
32                 cur = cur->next;
33                 pre = pre->next;
34             }
35         }
36         return node.next;
37     }
38 };