面试金典题2.1

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:

1. <strong> 输入</strong>：[1, 2, 3, 3, 2, 1]
2. <strong> 输出</strong>：[1, 2, 3]

复制代码

示例2:

1. <strong> 输入</strong>：[1, 1, 1, 1, 2]
2. <strong> 输出</strong>：[1, 2]

复制代码

提示：

• 链表长度在[0, 20000]范围内。
  
• 链表元素在[0, 20000]范围内。
  

进阶：
如果不得使用暂时缓冲区，该怎么解决？
这道题我一开始的思路新建一个链表，直接遍历判断链表是否存在当前遍历到的值，若未遍历到，则存入新的链表，若存在，则判断下一个值
leetcode代码

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* removeDuplicateNodes(ListNode* head) {  
12.         // 如果链表为空，则直接返回nullptr，因为没有节点需要处理  
13.         if(head == nullptr){  
14.             return head;  
15.         }  
16.          
17.         // 声明一个哈希表（unordered_set），用于存储已经出现过的节点值  
18.         // 初始时将头结点的值插入哈希表，因为头结点总是需要保留的（除非它是重复的，但这种情况在题目中未明确说明如何处理）  
19.         unordered_set<int> occurred = {head->val};  
20.          
21.         // pos指针用于遍历链表，初始时指向头结点  
22.         ListNode* pos = head;  
23.          
24.         // 遍历链表，直到pos的下一个节点为空（即链表末尾）  
25.         while(pos->next != nullptr){  
26.             // cur指针指向pos的下一个节点，即当前正在检查的节点  
27.             ListNode* cur = pos->next;  
28.               
29.             // 如果cur节点的值没有出现在哈希表中，说明它不是重复节点  
30.             if(!occurred.count(cur->val)){  
31.                 // 将cur节点的值添加到哈希表中，表示该值已经出现过  
32.                 occurred.insert(cur->val);  
33.                 // 移动pos指针到下一个节点，继续检查  
34.                 pos = pos->next;  
35.             }else{  
36.                 // 如果cur节点的值是重复的，则删除该节点  
37.                 // 通过将pos的next指针指向cur的next指针，实现跳过cur节点  
38.                 pos->next = pos->next->next;  
39.                 // 注意：这里不需要移动pos指针，因为pos的下一个节点（即原来的cur节点）已经被删除了  
40.             }  
41.         }  
42.          
43.         // 注意：在遍历结束后，pos指针会指向链表的最后一个非重复节点  
44.         // 由于链表末尾的next指针应该为nullptr，所以这里显式地将pos的next指针设置为nullptr  
45.         // 这一步其实是多余的，因为在遍历过程中，如果链表末尾的节点不是重复的，pos最终会指向它，并且它的next已经是nullptr了  
46.         // 但为了代码的清晰性和完整性，还是保留这一行代码  
47.         pos->next = nullptr;  
48.          
49.         // 返回处理后的链表头结点  
50.         return head;         
51.     }  
52. };

复制代码

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.   
10. class Solution {  
11. public:  
12.     /**  
13.      * 移除链表中所有重复的节点，只保留原始节点链表中每个值第一次出现的节点。  
14.      * @param head 链表的头节点  
15.      * @return 移除重复节点后的链表的头节点  
16.      */  
17.     ListNode* removeDuplicateNodes(ListNode* head) {  
18.         if (head == nullptr) {  
19.             // 如果链表为空，则直接返回nullptr  
20.             return nullptr;  
21.         }  
22.   
23.         ListNode* ob = head; // ob（outer block）用于遍历整个链表  
24.         while (ob != nullptr) {  
25.             ListNode* oc = ob; // oc（outer current）用于在ob指向的节点之后查找重复节点  
26.             while (oc->next != nullptr) {  
27.                 // 如果发现oc的下一个节点的值与ob相同，则移除oc的下一个节点  
28.                 if (oc->next->val == ob->val) {   
29.                     oc->next = oc->next->next;   
30.                 } else {  
31.                     // 如果没有发现重复，则oc继续向后移动  
32.                     oc = oc->next;  
33.                 }  
34.             }  
35.             // 完成ob节点之后所有重复节点的移除后，ob向后移动  
36.             ob = ob->next;  
37.         }  
38.         return head; // 返回修改后的链表的头节点  
39.     }  
40. };

复制代码

因为问到不使用暂时缓冲区，因此采用下面这种用时间换空间的做法。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。