剑指 复杂链表的复制

通过hashmap 保存节点，然后再去遍历串起链表。 hashmap存储节点时候需要新建一个randomlistnode。
注意返回的是 hashmap[pHead]

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if pHead==None:
            return None
        s=l=pHead
        hashmap={}
        while l!=None:

           hashmap[l]=RandomListNode(l.label)
           l=l.next
        while s!=None:
            node=hashmap[s]
            #print(node.label)
            if s.next:
                node.next=hashmap[s.next]
            else:
                node.next=None
            if s.random:
                node.random=hashmap[s.random]
            else:
                node.random=None
            s=s.next





        return hashmap[pHead]

先将链表节点每个复制一下，然后连在当前节点后面，然后再遍历一次，将random指针安排好，最后将链表拆分，注意先拆分"原链表"。

class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if pHead==None:
            return None

        l=pHead
        while l!=None:
            node=RandomListNode(l.label)

            node.next=l.next
            l.next=node
            l=node.next


        s=pHead
        while s!=None and s.next!=None:
            if s.random:
                s.next.random=s.random.next
            s=s.next.next
        result=p=pHead.next
        #result=RandomListNode(0)
        f=pHead
        while p.next!=None:
            f.next=f.next.next
            p.next=p.next.next

            p=p.next
            f=f.next
        f.next=None
        return result