輸入一個復(fù)雜鏈表（每個節(jié)點中有節(jié)點值，以及兩個指針混移，一個指向下一個節(jié)點，另一個特殊指針指向任意一個節(jié)點）。
/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
// 復(fù)制節(jié)點
void duplicate(RandomListNode* pHead)
{
RandomListNode* idx = pHead;
while(idx){
RandomListNode* duplicate_node = new RandomListNode(idx->label);
duplicate_node->next = idx->next;
idx->next = duplicate_node;
idx = duplicate_node->next;
}
}
// 調(diào)整復(fù)制后的節(jié)點的random
void adjust_dp(RandomListNode* pHead)
{
RandomListNode* idx = pHead;
RandomListNode* duplicate_node = idx->next;
while(idx){
duplicate_node = idx->next;
if(idx->random){
duplicate_node->random = idx->random->next;
}
idx = duplicate_node->next;
}
}
// 分離大鏈表
RandomListNode* split_list(RandomListNode* pHead)
{
RandomListNode* pHead_dp = pHead->next;
RandomListNode* idx = pHead, *idx_dp = pHead_dp;
while(idx->next->next){
idx->next = idx_dp->next;
idx_dp->next = idx_dp->next->next;
idx = idx->next;
idx_dp = idx_dp->next;
}
idx->next = NULL;
return pHead_dp;
}
RandomListNode* Clone(RandomListNode* pHead)
{
if(!pHead){return NULL;}
// 復(fù)制節(jié)點
duplicate(pHead);
// 調(diào)整復(fù)制節(jié)點的random指針
adjust_dp(pHead);
// 分離復(fù)制的鏈表
return split_list(pHead);
// return pHead;
}
};
