25. 复杂链表的复制

25. 复杂链表的复制

题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路
注意本题的要点在于，输出结果中不要返回参数中的节点引用，所以不能直接将参数节点返回结果，而是要通过遍历的方式建立拥有新的节点的新链表。
解题思路：
1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
3、拆分链表，将链表拆分为原链表和复制后的链表
思路图如下所示：



代码也分3步来解决这个问题。分别是：(要注意节点的next为空的情况)
第1次遍历，复制节点
第2次遍历，复制random指针
第3次遍历，拆分链表

代码实现

# -*- 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 not pHead:
            return pHead
        # 第1次遍历，复制节点
        head = pHead # 把参数复制到head中，免得后续操作影响pHead
        while(head):
            newNode = RandomListNode(head.label)
            newNode.next = head.next
            head.next = newNode
            head = newNode.next
        # 第2次遍历，复制random指针
        head = pHead
        while(head):
            newNode = head.next
            if head.random:
                newNode.random = head.random.next
            head = newNode.next
        # 第3次遍历，拆分链表
        head = pHead
        newHead = head.next # newHead是新链表的表头指针，先固定下来
        while(head):
            newNode = head.next
            head.next = newNode.next
            head = newNode.next
            if(head == None):
                newNode.next = None
            else:
                newNode.next = head.next
        return newHead