网站建设公司年终总结,网站1g空间多少钱,建店前期网站开通怎么做分录,互联网保险的风险【问题描述】[简单]
编写代码#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]范围内。
进阶如果不得使用临时缓冲区该怎么解决
【解答思路】
1. Set/哈希集合
对给定的链表进行一次遍历并用一个哈希集合HashSet来存储所有出现过的节点val
时间复杂度O(N) 空间复杂度O(N)
class Solution {public ListNode removeDuplicateNodes(ListNode head) {if (head null) {return head;}SetInteger occurred new HashSetInteger();occurred.add(head.val);ListNode pos head;// 枚举前驱节点while (pos.next ! null) {// 当前待删除节点ListNode cur pos.next;if (occurred.add(cur.val)) {pos pos.next;} else {pos.next pos.next.next;}}pos.next null;return head;}
}
另一种写法 public ListNode removeDuplicateNodes(ListNode head) {if(head null){return null;}SetInteger set new HashSet();ListNode pre head;ListNode cur head.next;set.add(head.val);while(cur!null){if(set.contains(cur.val) ){pre.next cur.next;// 连接到最后的nullcur cur.next;}else{set.add(cur.val);pre cur;cur cur.next;}}return head;}2. 两重循环冒泡排序 进阶解法
在给定的链表上使用两重循环其中第一重循环从链表的头节点开始枚举一个保留的节点这是因为我们保留的是「最开始出现的节点」。第二重循环从枚举的保留节点开始到链表的末尾结束将所有与保留节点相同的节点全部移除。 第一重循环枚举保留的节点本身而为了编码方便第二重循环可以枚举待移除节点的前驱节点方便我们对节点进行移除。这样一来我们使用「时间换空间」的方法就可以不使用临时缓冲区解决本题了。
时间换空间
时间复杂度O(N^2) 空间复杂度O(1)
class Solution {public ListNode removeDuplicateNodes(ListNode head) {ListNode ob head;while (ob ! null) {ListNode oc ob;while (oc.next ! null) {if (oc.next.val ob.val) {oc.next oc.next.next;} else {oc oc.next;}}ob ob.next;}return head;}
}
【总结】
1.枚举前驱节点 删除节点方便 2.时间空间相互tradeoff
3.链表题目画图 切忌心烦意乱
转载链接https://leetcode-cn.com/problems/remove-duplicate-node-lcci/solution/yi-chu-zhong-fu-jie-dian-by-leetcode-solution/
