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

Posted on |

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

题目

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

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

方法

方法1：不采用字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if not head:
            return None

        pre = head
        while pre:
            temp = pre.next
            pre.next = RandomListNode(pre.label)
            pre.next.next = temp
            pre = pre.next.next

        pre = head
        while pre:
            if pre.random:
                pre.next.random = pre.random.next
            pre = pre.next.next

        res = head.next
        cur = res
        pre = head
        while pre:
            pre.next = pre.next.next
            if cur.next:
                cur.next = cur.next.next
            pre = pre.next
            cur = cur.next

        return res
```        


#### 方法2：采用字典

```python
# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        # import copy
        # res = copy.deepcopy(head)
        # return res
        if not head:
            return

        res = RandomListNode(head.label)
        n1 = head.next
        n2 = res
        lists = {head:res}
        while n1:
            n2.next = RandomListNode(n1.label)
            lists[n1] = n2.next
            n1 = n1.next
            n2 = n2.next
        lists[None] = None
        n1 = head
        n2 = res
        while n1:
            n2.random = lists[n1.random]
            n2 = n2.next
            n1 = n1.next
        return res

更容易理解，这个版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def copyRandomList(self, head):
        if not head:
            return head
        copy = RandomListNode(head.label)
        dic = {head: copy}
        while head:
            tcopy = dic[head]
            if head.next:
                if head.next not in dic:
                    dic[head.next] = RandomListNode(head.next.label)
                tcopy.next = dic[head.next]
            if head.random:
                if head.random not in dic:
                    dic[head.random] = RandomListNode(head.random.label)
                tcopy.random = dic[head.random]
            head = head.next
        return copy