复杂链表的复制

输入：
{1,2,3,4,5,3,5,#,2,#}
返回值：
{1,2,3,4,5,3,5,#,2,#}

方法1：创建新节点直接存
方法2：原节点上操作再分离(1->1'->2->2')

方法2思路：
1.在原节点插入副本节点
2.复制random指针(很关键的一步是copy->random=cur->random->next)指向当前指针的随机指针中的下一节点
3.分离

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if (!pHead) {
            return NULL;
        }
        //1.创建原节点副本，放到原节点后
        RandomListNode *cur = pHead;
        while (cur) {
            RandomListNode *cpyNode = new RandomListNode(-1);
            //创建新节点
            cpyNode->label = cur->label;//传递label
            cpyNode->next = cur->next;//传递next指针
            //插入新节点
            cur->next = cpyNode;//插入节点
            cur = cpyNode->next;//指针指向下一节点
        }
        //2.构造随机指针
        RandomListNode *tmp = pHead;//指到头部
        RandomListNode *tmp2;
        while (tmp) {
            tmp2 = tmp->next;
            if (tmp->random) {
                tmp2->random = tmp->random->next;//很关键，注意是指向random->next
            }
            tmp = tmp2->next;
        }
        //3.分成两个链表
        RandomListNode *p1 = pHead;//1
        RandomListNode *p2;
        RandomListNode *clone = pHead->next;//2
        while (p1) {
            p2 = p1->next;
            p1->next = p2->next;
            p1 = p1->next;
            if (p1) {//判断是否有下一节点
                p2->next = p1->next;
            }
        }
        return clone;
    }
};

# -*- 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 None
        cur = pHead
        while cur:#1.复制val和next
            cpyNode = RandomListNode(-1)
            cpyNode.label = cur.label
            cpyNode.next = cur.next
            cur.next = cpyNode
            cur = cpyNode.next
        cur = pHead
        while cur:#复制random
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        cur = pHead
        clone = pHead.next
        while cur.next://拆分
            tmp = cur.next
            cur.next = tmp.next
            cur = tmp
        return clone