网站建设一般需要什么功能,网站开发的流程 知乎,做购物车网站多少钱,自己做下载网站题目描述
编写代码#xff0c;移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入#xff1a;[1, 2, 3, 3, 2, 1] 输出#xff1a;[1, 2, 3]
-示例2:
输入#xff1a;[1, 1, 1, 1, 2] 输出#xff1a;[1, 2]
提示#xff1a;
链表长度在[0, 20000]范…题目描述
编写代码移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入[1, 2, 3, 3, 2, 1] 输出[1, 2, 3]
-示例2:
输入[1, 1, 1, 1, 2] 输出[1, 2]
提示
链表长度在[0, 20000]范围内。 链表元素在[0, 20000]范围内。
进阶
如果不得使用临时缓冲区该怎么解决
解题思路与代码
首先这道题于本质上是要让你删除一些重复的节点。那么删除一个节点需要做哪些操作呢
首先本题给的是单链表。如果要删除某个节点则要找到当前节点的前驱节点使前驱节点的next指针指向当前节点的下一个节点最后将当前节点的内存释放掉至此删除某个节点的操作才算正式完成。
哈希法
因为要删除一个节点我们就要用该节点的前驱节点去指向该节点的下一个节点。所以我们就先设立一个要被处理元素的前驱节点然后依次遍历被处理元素这个节点。如果被处理元素需要被删除那我们直接用前驱节点删除好了。
为什么要叫哈希法呢这是因为用到了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) return head;unordered_setint set {head-val};ListNode* pos head;while(pos-next ! nullptr){ListNode* cur pos-next; //即将要删除的节点if(set.find(cur-val) set.end()){set.insert(cur-val);pos cur;}else{pos-next cur-next;delete cur;}}return head;}
};复杂度分析 时间复杂度O(N),因为只用了一个while循环其中N是给定链表的节点数目。 空间复杂度O(N),因为最坏情况下集合中的元素都不相同我们要存储所有的元素到集合中。
进阶不使用临时缓冲区
说到不使用临时缓冲区其实它的意思就是让我直接对链表进行操作。那么如果想象成删除一个string中重复出现的字符了话这道题其实用两个for循环暴力破解了就行。但这道题是在链表上进行操作我们就要将双层for循环去改成双层while循环。
这解题思路还是与哈希法类似一共需要设立3个节点。 第一个节点作为外层循环遍历节点与被处理元素的对照组初始值head。 第二个节点作为被处理元素的前驱节点初始值也第一个节点。 第三个节点作为被处理元素初始值为第二个节点-next。
具体实现的看代码细节
/*** 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) return head;ListNode* pos head; //对照节点while(pos ! nullptr){ListNode* pre pos; //被处理元素的前驱节点ListNode* cur pre-next; //被处理元素while(cur ! nullptr){if(pos-val ! cur-val){pre cur;}else{pre-next cur-next;}cur cur-next;}pos pos-next;}return head;}
};复杂度分析 时间复杂度O(N^2)其中N代表所给链表的节点数。用了两个while循环。 空间复杂度O(1)因为只用到了几个临时变量。
优化双层遍历法
这次代码对应上次的优化是只设置了两个节点用来变量。我们将pos作为外层遍历节点与对照组节点将cur作为前驱节点将cur-next作为被处理节点。
减少了一个临时变量的设置优化了一行代码但是代码的易读性变差并且代码易错性增强。
具体实现看代码
/*** 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) return head;ListNode* pos head; while(pos ! nullptr){ListNode* cur pos; while(cur-next ! nullptr){ if(cur-next-val pos-val)cur-next cur-next-next; elsecur cur-next;}pos pos-next;}return head;}
};复杂度分析 时间复杂度O(N^2)其中N代表所给链表的节点数。用了两个while循环。 空间复杂度O(1)因为只用到了几个临时变量。
