Python 数据结构之链表 —— （四）移除重复项及带随机指针的链表复制

zltzlt

来源于 CSDN

Python 数据结构之链表 —— （四）移除重复项及带随机指针的链表复制

这一篇是 LeetCode 上关于链表的两道题目，难度都是中等，但是我认为难度很大了，尤其是复制链表一题，思路星期。

题目 1

82. 删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

输入：1->2->3->3->4->4->5
输出：1->2->5

示例 2：

输入：1->1->1->2->3
输出：2->3

题目解析

要注意 83 题是保留一项，十分简单，就不解析了；而这道题威力加强，如果有两项是重复的，就全都删掉。先看代码再解释：

1. class Solution:
   
2.     def deleteDuplicates(self, head):
   
3.         if head is None or head.next is None:
   
4.             return head
   
5.         fhead = ListNode(0)
   
6.         fhead.next = head
   
7.         pre = fhead
   
8.         cur = head
   
9. 
   
10.         while cur:
    
11.             while cur.next and cur.val == cur.next.val:
    
12.                 cur = cur.next
    
13.             if pre.next == cur:  # 如果只此一个值，不删除，pre 后移
    
14.                 pre = cur
    
15.             else:
    
16.                 pre.next = cur.next  # 如果不只一个，删除这些结点，pre 暂不后移
    
17.             cur = cur.next
    
18.         return fhead.next

复制代码

因为头结点可能会被删掉，先加一个结点；判断相邻两项的值，停留在重复项的最后一个位置（或者就原地不动了），通过 pre 指针与当前指针的关系判断两种情况。

理解解题思想很关键~

题目 2

138. 复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

这一链表结点的定义看下面代码，这一题其实蛮有难度，甚至题目还如此简洁，测试样例也看不懂。

复制问题的关键在于，挨个复制结点时，结点的 next 本身复制了结点间的连接关系并赋予 label 值，创建了一个 label 和 next 属性都一样的新结点。

而 random 指向另一结点时，却不能通过复制 label 来解决，因为其指向一个已存在的结点（该链表中的），你复制的话就分叉了而没有指向该链表中的结点（或者指向了原链表中的结点）。

下面的解决方案有点牛逼，看后面的大神的方法写的：

1. # Definition for singly-linked list with a random pointer.
   
2. # class RandomListNode(object):
   
3. #     def __init__(self, x):
   
4. #         self.label = x
   
5. #         self.next = None
   
6. #         self.random = None
   
7. 
   
8. class Solution(object):
   
9.     def copyRandomList(self, head):
   
10.         if head is None:
    
11.             return None
    
12.         p = head
    
13.         while p:
    
14.             tmp = p.next
    
15.             p.next = RandomListNode(p.label)
    
16.             p.next.next = tmp
    
17.             p = tmp
    
18.         p = head
    
19.         while p:
    
20.             if p.random:
    
21.                 p.next.random = p.random.next
    
22.             p = p.next.next
    
23.         newhead = RandomListNode(0)
    
24.         p = head
    
25.         q = newhead
    
26.         while p:
    
27.             tmp = p.next.next
    
28.             q.next = p.next
    
29.             q = q.next
    
30.             p.next = tmp
    
31.             p = tmp
    
32.         return newhead.next

复制代码

这一方法用了三次循环，结合下图理解一下。

该方法的时间复杂度为 O(n)，空间复杂度 O(1)，几乎不占用额外的内存空间。

                               
登录/注册后可看大图

当然这一问题有一个更直观的解决方法，就是哈希表，第一次遍历存储各结点，第二遍设置随机指针，其空间复杂度为 O(n)。

Python 中用字典也可以解决这个问题，可看如下代码：

1. class Solution:
   
2.     # @param head, a RandomListNode
   
3.     # @return a RandomListNode
   
4.     def copyRandomList(self, head):
   
5.         dic = collections.defaultdict(lambda: RandomListNode(0))
   
6.         dic[None] = None
   
7.         n = head
   
8.         while n:
   
9.             dic[n].label = n.label
   
10.             dic[n].next = dic[n.next]
    
11.             dic[n].random = dic[n.random]
    
12.             n = n.next
    
13.         return dic[head]

复制代码

_2_

链表结构是在 Python 里面有定义，还是自定义的？

zltzlt

_2_ 发表于 2020-3-12 14:51
链表结构是在 Python 里面有定义，还是自定义的？

自定义的

_2_

zltzlt 发表于 2020-3-12 14:52
自定义的

oh，哪天花点时间讲讲吧

Joy187

emm……这个方法可以吗？

1. n=input()
   
2. b=[]
   
3. k=0
   
4. for i in range(0,len(n)):
   
5.                if(n.count(n[i])==1):
   
6.                    b.append(n[i])
   
7. for i in range(0,len(b)-1):
   
8.     print("{0}->".format(b[i]),end='')
   
9. print(b[len(b)-1])
   

复制代码