2019-07-18 剑指复杂链表的复制

40min 测试现行 pycharm 本地跑通之后 线上一次通过

1.not PHead 是空的搞错了
2.指针没有往下移动，循环没有跳出
3.key指为None的时候没有键值

# -*- 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):
        dummy=RandomListNode(None)
        cur=dummy
        dic={}
        original_p=pHead
        while original_p:
            tmp=RandomListNode(original_p.label)
            cur.next=tmp
            cur=cur.next
            dic[original_p]=tmp
            original_p=original_p.next
        cur=dummy.next
        while pHead:
            if pHead.random:cur.random=dic[pHead.random]  # 如果random是None会没有这个键
            pHead=pHead.next
            cur=cur.next
        return dummy.next

第二种方法是复制到当前节点的下一个节点，也是hash的思想，不用再去遍历寻找这个节点
1.经常忘记指针循环
2.指针操作很容易错。最后容易忘了把指针指向None
3.bool值取反 not

本地测试和Solution比较没有差别，但是平台报错 空？？根本无法检查吗，报空 原来是PHead不能改变 50min
重新检查6min发现问题

class Solution2():
    def Clone(self,pHead):
        # 复制节点，并放在每个节点的next
        cur=pHead
        while cur:
            new=RandomListNode(cur.label)
            second=cur.next
            cur.next=new
            new.next=second
            cur=second
        # 复制random
        cur=pHead
        while cur:
            # print(cur.label)
            if cur.random:cur.next.random=cur.random.next # 卧槽调试二十分钟是这里错了，cur.next.random，还是靠中间结果的打印，缩小范围
            cur=cur.next.next # 时隔二十天重新检查了一遍发现是这里出了问题
        # 剪下新复制的链表
        dummy=RandomListNode(None)
        dummy2=RandomListNode(None)
        cur=pHead
        even=False
        new_cur=dummy
        old_cur=dummy2
        while cur:
            # print(cur.label)
            if even:
                new_cur.next=cur
                new_cur=new_cur.next
            else:
                old_cur.next=cur
                old_cur=old_cur.next
            even=not even  # 为何最后结果为空，其他看了一遍应该都对的，所以应该是~even有错
            cur=cur.next
        old_cur.next=None # 老链表里的最后一个还与新链表里藕断丝连
        return dummy.next