LeetCode: Copy List with Random Pointer

思路分析

一道非常巧妙的链表操作题目，在《剑指Offer》书上见过，原来也是原封不动地照抄LeetCode，鄙视之。这题的核心思路在于，既然要求链表的就地复制，那么我们不妨在原链表中每一个节点的后面增加一个新的节点，这样就可以很轻易地把随机的转移关系加进去，因为在新链表中需要转移到的节点，就是原本转移到节点的下一个节点。最后再将这个已经长度倍增了的链表重新拆分为两个链表，返回新建的那个即可。

代码

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if ( head == NULL ) return NULL;
        RandomListNode *p = head;
        while ( p != NULL ) {
            RandomListNode *next = p->next;
            p->next = new RandomListNode(p->label);
            p->next->next = next;
            p = next;
        }
        p = head;
        while ( p != NULL ) {
            if ( p->random != NULL )
                p->next->random = p->random->next;
            p = p->next->next;
        }
        p = head;
        RandomListNode *result = NULL;
        while ( p != NULL ) {
            RandomListNode *new_node = p->next;
            if ( result == NULL ) result = new_node;
            p->next = new_node->next;
            if ( p->next != NULL )
                new_node->next = p->next->next;
            else
                new_node->next = NULL;
            p = p->next;
        }
        return result;
    }
};