leetcode c++未初始化_leetcode的python实现(面试题 02.01) 移除重复节点

【移除重复节点】

---

题目描述
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
 输入：[1, 2, 3, 3, 2, 1]
 输出：[1, 2, 3]
示例2:
 输入：[1, 1, 1, 1, 2]
 输出：[1, 2]
提示：
链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。
进阶：
如果不得使用临时缓冲区，该怎么解决？

---

思路 1.哈希表．使用缓存，初始化一个哈希集合check，用来记录已经出现的链表节点值，下一次再出现该值，则应该跳过该节点．时间复杂度O(n)，空间复杂度为O(n)． 2.两次遍历．不使用额外的缓存区，对链表遍历两遍，设置两个指针p1,p2,其中p1指针为外循环，p2为内循环，时间复杂度为O(n^2),空间复杂度为O(1).
方法2虽然正确，但是时间复杂度较高，在官网运行会提示超时．

---

1.哈希表．

# Definition for singly-linked list.class ListNode:    def __init__(self, x, next=None):        self.val = x        self.next = nextclass Solution:    def removeDuplicateNodes(self, head: ListNode) -> ListNode:        if not head:            return head        cur = head        check = set()        check.add(head.val)        while cur.next:            if cur.next.val  not in check:                check.add(cur.next.val)                cur = cur.next            else:                cur.next = cur.next.next        return head

---

2.两次遍历．

# #暴力法双重循环，超时无法通过class Solution:    def removeDuplicateNodes(self, head: ListNode) -> ListNode:        if not head:            return head        p1 = head        while p1:            p2 = p1            while p2.next:                if p2.next.val != p1.val:                    p2 = p2.next                else:                    p2.next = p2.next.next            p1 = p1.next        return head

---

点击左下角【阅读原文】查看leetcode官网本题描述

【往期文章回顾】

---

链表

1. 剑指offer的python实现(1)-从尾到头打印链表的值

2. 剑指offer的python实现(6)-反转链表

3. 剑指offer的python实现(15)-链表中倒数第k个结点

4. 剑指offer的python实现(16)-合并两个排序的链表

5. 剑指offer的python实现(18)-删除链表中重复的结点

6. 剑指offer的python实现(20)-链表中的环的入口接点

7. 剑指offer的python实现(23)-两个链表的第一个公共结点

8. 剑指offer的python实现(27)-复杂链表的复制

9. 剑指offer的python实现(29)-二叉搜索树与双向链表

10. leetcode-19. 删除链表的倒数第N个节点

11. leetcode的python实现-(206)反转链表和(92)反转链表II

12. leetcode的python实现-(876)链表的中间结点

13. leetcode的python实现-(148)排序链表

14. leetcode的python实现-(328)奇偶链表

15. leetcode的python实现-(61)旋转链表

---

二叉树

1. 剑指offer的python实现(3)-重建二叉树

2. 剑指offer的python实现(4)-二叉树层级遍历

3. 剑指offer的python实现(5)-二叉搜索树的后序遍历序列

4. 剑指offer的python实现(21)-二叉树的镜像

5. 剑指offer的python实现(22)-树的子结构

6. 剑指offer的python实现(25)-二叉树中和为某一值的路径

7. 剑指offer的python实现(30)-二叉树的深度

8. 剑指offer的python实现(33)-平衡二叉树

9. 剑指offer的python实现(38)-二叉树的下一个结点

10. 剑指offer的python实现(39)-对称的二叉树

11. 剑指offer的python实现(40)-二叉搜索树的第k个结点

12. leetcode－二叉树的前、中、后序遍历和层序遍历python实现

13. leetcode－N叉树的前、后序遍历和层序遍历python实现

14. leetcode(98)-验证二叉搜索树

15. leetcode(235)python实现- 二叉搜索树的最近公共祖先

16. leetcode的python实现-(449)序列化和反序列化二叉搜索树

---

数组

1. leetcode(560)python实现-和为k的子数组

2. 剑指offer的python实现(46)-构建乘积数组

3. 剑指offer的python实现(35)-把数组排成最小的数

4. 剑指offer的python实现(32)-连续子数组的最大和

5. 剑指offer的python实现(31)-数组中出现次数超过一半的数字

6. 剑指offer的python实现(17)-调整数组奇偶数顺序

7. 剑指offer的python实现(9)-旋转数组的最小数字

8. 找出一维数组中的重复值-python实现

9. leetcode－1.两数之和

10. leetcode的python实现-(15)三数之和

11. leetcode的python实现-(18)四数之和

---

字符串

1. 剑指offer的python实现(36)-第一个只出现一次的字符位置

2. 剑指offer的python实现(42)-左旋转字符串

3. 剑指offer的python实现(45)-把字符串转换成整数

4. leetcode的python实现-(面试题46).把数字翻译成字符串

5. leetcode的python实现-(125)验证回文串

6. leetcode的python实现-(680) 验证回文字符串Ⅱ

---

栈和队列

1. 剑指offer的python实现(7)-用两个栈实现队列

2. 剑指offer的python实现(8)-栈的压入弹出序列

3. 剑指offer的python实现(28)-包含min函数的栈

4. leetcode的python实现-(739)每日温度

5. leetcode的python实现-(496)下一个更大元素 I

6. leetcode的python实现-(503)下一个更大元素 II

---

动态规划

1. 剑指offer的python实现(10)-斐波那契数列

2. 剑指offer的python实现(11)-跳台阶

3. 剑指offer的python实现(12)-变态跳台阶

4. leetcode的python实现-(62) 不同路径

5. leetcode的python实现-(63) 不同路径 II

6. leetcode的python实现-(64) 最小路径和

---

排序算法

1. 冒泡排序、选择排序、插入排序、快速排序的python实现
2. 归并排序、堆排序的python实现

3. 计数排序、桶排序、基数排序的python实现

---

长按二维码关注公众号，获取更多内容

点击留言