C++刷leetcode(面试题 02.01. 移除重复节点)【数据结构】

糖逗

题目描述：

1. 
   
2. 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
   
3. 
   
4. 示例1:
   
5. 
   
6. 输入：[1, 2, 3, 3, 2, 1]
   
7. 输出：[1, 2, 3]
   
8. 示例2:
   
9. 
   
10. 输入：[1, 1, 1, 1, 2]
    
11. 输出：[1, 2]
    
12. 提示：
    
13. 
    
14. 链表长度在[0, 20000]范围内。
    
15. 链表元素在[0, 20000]范围内。

复制代码

1. #include <iostream>
   
2. #include <map>
   
3. using namespace std;
   
4. 
   
5. 
   
6. struct ListNode{
   
7.         int val;
   
8.         ListNode* next;
   
9.         ListNode(int x) :val(x), next(NULL){
   
10.         }
    
11. };
    
12. 
    
13. 
    
14. void PrintList(ListNode*input){
    
15.         ListNode*temp = input;
    
16.         while(temp -> next){
    
17.                 temp = temp -> next;
    
18.                 cout << temp -> val << " ";
    
19.         }
    
20.         cout << endl;
    
21.         cout << "-------------" << endl;
    
22. }
    
23. 
    
24. 
    
25. ListNode* solution(ListNode* input){
    
26.         map<int,int> store;
    
27.         ListNode* temp = input -> next;
    
28.     ListNode*pre = input -> next;
    
29.         while(temp != NULL){
    
30.                 store[temp->val] ++;
    
31.                 if(store[temp->val] > 1){
    
32.                         pre -> next = temp -> next;
    
33.                         temp = temp -> next;
    
34.             continue;
    
35.                 }
    
36.                 pre = temp;
    
37.         temp = temp -> next;
    
38.         }
    
39.     return input;
    
40. }
    
41. 
    
42. int main(void){
    
43.         ListNode*input = new ListNode(0);
    
44.         ListNode*temp = input;
    
45.         cout << "please send numbers for the first singleList:" << endl;
    
46.     int number;
    
47.     while(cin >> number){
    
48.             ListNode* node = new ListNode(number);
    
49.             temp -> next = node;
    
50.             temp = node;
    
51.     }
    
52.     PrintList(input);
    
53.     ListNode* new_root = solution(input);
    
54.     PrintList(new_root);
    
55.     return 0;
    
56. }

复制代码

注意事项：
1.基本数据结构考察。