剑指offer-复杂链表的复制

题目描述

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

/*
题目难点在特殊指针的指向，如何解决？
1.在每个节点后面添加一个新节点，（新节点和前面的那个节点一模一样）
2.新节点的特殊指针指向它前面节点特殊指针指向的节点的后一个节点
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==NULL){
            return NULL;
        }
        RandomListNode* q = pHead;
        while(q!=NULL)
        {
            RandomListNode* q1 = new RandomListNode(q->label);
            q1->next = q->next;
            q->next = q1;
            q = q1->next;
        }
        //将特殊指针指好
        RandomListNode* p = pHead;
        RandomListNode* p1 = pHead->next;
        while(p!=NULL)
        {
            if(p->random!=NULL){
                p1->random = p->random->next;
            }
            p = p1->next;
            p1 = p->next;
        }
        //拆分链表
        RandomListNode* newpHead = pHead->next;
        RandomListNode *tmp;
        RandomListNode* cur = pHead;
        while(cur->next){
            tmp = cur->next;
            cur->next =tmp->next;
            cur = tmp;
        }
        return newpHead;
    }
};