复杂链表的复制
示例
代码语言：javascript复制输入：
{1,2,3,4,5,3,5,#,2,#}
返回值：
{1,2,3,4,5,3,5,#,2,#}思路
代码语言：javascript复制方法1：创建新节点直接存
方法2：原节点上操作再分离(1->1'->2->2')
方法2思路：
1.在原节点插入副本节点
2.复制random指针(很关键的一步是copy->random=cur->random->next)指向当前指针的随机指针中的下一节点
3.分离题解
代码语言：javascript复制/*
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
