题目描述
示例1:
输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
示例2:
输入：[1, 1, 1, 1, 2]
输出：[1, 2]
提示：
- 链表长度在[0, 20000]范围内。
- 链表元素在[0, 20000]范围内。
进阶：
- 如果不得使用临时缓冲区，该怎么解决？
解题思路与代码
- 这道题是一道比较简单的题。主要考验的是你对链表这种数据结构的操作能力。比如如何删除一个节点。其次呢，还可能考察了你如何使用哈希映射去去重的能力。
具体呢这道题有两种做法，接下来就让我们仔细分析一下这两种做法各有什么区别。
方案一：哈希映射找出多余的节点后删除
- 这种方法主要就是依靠哈希映射去看看元素有没有被重复添加，我们在这里面使用到了unordered_set这种数据结构。之后我们遍用双指针法去遍历整个链表，去删除重复的元素
具体的代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeDuplicateNodes(ListNode* head) {
if(head == nullptr || head->next == nullptr) return head;
unordered_set<int> set;
ListNode * prev = nullptr;
ListNode * curr = head;
while(curr){
if(set.count(curr->val)){
ListNode * temp = curr->next;
prev->next = temp;
ListNode * dNode = curr;
curr = curr->next;
dNode = nullptr;
delete dNode;
continue;
}
set.insert(curr->val);
prev = curr;
curr = curr->next;
}
return head;
}
};
复杂度分析
时间复杂度：
- 我们只是遍历了一遍链表，所以时间复杂度是O(n)
空间复杂度：
- 我们用到了unordered_set数据结构，最多存储n个数据，所以空间复杂度也是O(n)
方案二：多指针暴力破解
- 这种方法其实就更无脑了。有点像双层for循环。只不过我们这里用while循环，使用多个指针，依次对比每一个元素是否重复，之后删除掉
具体代码如下：
class Solution {
public:
ListNode* removeDuplicateNodes(ListNode* head) {
if(head == nullptr || head->next == nullptr) return head;
ListNode * slow = head;
while(slow != nullptr){
ListNode * prev = slow;
ListNode * curr = slow->next;
while(curr != nullptr){
if(slow->val == curr->val){
ListNode * temp = curr->next;
delete curr;
prev->next = temp;
curr = temp;
continue;
}
prev = curr;
curr = curr->next;
}
slow = slow->next;
}
return head;
}
};
复杂度分析
时间复杂度：因为是双层遍历，所以时间复杂度为O(n^2)
空间复杂度：因为没有使用多余的数据结构，所以空间复杂度是O(1)
总结
-
基础数据结构理解：理解和处理链表是编程和数据结构中的基本技能。你需要了解如何遍历链表、如何修改链表节点之间的连接，以及如何在链表中插入和删除节点。
-
编程技巧：这道题需要你实现一个功能，去除链表中的重复元素。这既可以考察你对于基础算法的理解，也可以考察你编程的技巧和代码质量，例如，你能否写出没有内存泄漏的代码。
-
空间和时间复杂度权衡：这道题的进阶部分是在不使用额外空间的情况下解决问题，这就需要你去考虑如何在空间和时间复杂度之间做出权衡。在许多真实世界的问题中，空间和时间常常是一对矛盾，有时需要牺牲时间来换取空间，有时则需要牺牲空间来换取时间。
-
问题解决策略：最初的问题可以用哈希表简单解决，但进阶问题则需要改变策略。这能帮助你学会如何针对不同的约束条件选择不同的解决方案，这在实际的软件开发工作中是非常重要的。
总的来说，这道题是一道非常好的综合性编程题，可以全面考察你的编程能力。
最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。