剑指offer 25. 复杂链表的复制

原题

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

Reference Answer

解题思路:

这个题是分而治之的做法，很好玩。思想是在原来的链表每个节点后面都复制了一个同样的节点，再修改其指针，最后把偶数节点都抽出来，作为新的复杂链表。

# -*- 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
        self.cloneNodes(pHead)
        self.connectSiblingNodes(pHead)
        return self.reconnectNodes(pHead)
    def cloneNodes(self, pHead):
        pNode = pHead
        while pNode:
            pCloned = RandomListNode(pNode.label)
            pCloned.next = pNode.next
            pNode.next = pCloned
            pNode = pCloned.next
            
    def connectSiblingNodes(self, pHead):
        pNode = pHead
        while pNode:
            pclone = pNode.next
            if pNode.random:
                pclone.random = pNode.random.next
            pNode = pclone.next
    def reconnectNodes(self, pHead):
        pNode = pHead
        pCloneHead = None
        pCloneNode = None
        if pNode:
            pCloneHead = pCloneNode = pNode.next
            pNode.next = pCloneNode.next
            pNode = pNode.next
        while pNode:
            pCloneNode.next = pNode.next
            pCloneNode = pCloneNode.next
            pNode.next = pCloneNode.next
            pNode = pNode.next
        return pCloneHead
            

参考答案：https://blog.csdn.net/fuxuemingzhu/article/details/79622359