LeetCode：复制带随机指针的链表

面试题35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

思路：
1）原始1->2->3->N
2）复制成为 1->1->2->2->3->3`->N
3）在将随机指针进行复制
4）将链表拆分成原链表和复制的链表

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==NULL)
            return NULL;

        /*Node* org = head;
        Node *copy = NULL;
        while (org != NULL)
        {
            copy = org;
            copy->next = org->next;
            org->next = copy;
            org = org->next->next;
        }*/
        //复制成 长链表
        Node *org = head;
        Node *pnext = NULL;
        while (org != NULL)
        {
            pnext = org->next;
            Node* tmp = new Node(org->val);
            tmp->next = pnext;
            org->next = tmp;
            org = pnext;
        }
        // 复制随机指针
        org = head;
        Node *copy = head->next;
        while (org != NULL)
        {
            //如果随即指针为空 需要判断
            copy->random = org->random? org->random->next :NULL;
            org = copy->next;
            copy = org?org->next:org;
        }
        //拆分长链表
        org = head;
        copy = head->next;
        Node *phead = copy;
        while (org != NULL)
        {
            org->next = copy->next;
            org = org->next;
            // 最后一个结点 org为空  copu->next也为空
            copy->next = org?org->next:org;
            copy = copy->next;
        }
        return phead；
    }
};

注意：代码块中注释的代码。看似也是复制成长链表，但是要记住指针不是结点，copy = org; 这种操作其实是 copy和org都指向了同一个Node，也就是存储的值都是一样的，是Node的地址，而不是copy新建了一个和org指向的结点一样的新节点。

所以copy->next = org->next; 其实是copy->next == org->next; ！！！