给大家推荐一道leetcode上的面试题，这道题的详细解说在《剑指offer》的P149页有思路解说。假设你手头有这本书。建议翻阅。

题目链接 here

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

RandomList中。每一个节点不光有一个next指针。并且每一个链表节点都有一个random指针。随机指向链表中的一个节点，让你复制这个链表，节点的C++定义例如以下。

/**

 * Definition for singly-linked list with a random pointer.

 * struct RandomListNode {

 *     int label;

 *     RandomListNode *next, *random;

 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}

 * };

 */

看到这个题目，预计非常多人的第一反应是，先把这个单链表复制出来，然后挨个找random指向的节点。细致想想这样效率非常低。复制链表非常快。但确定每一个节点的random指针就不easy了，用这样的方法的话。每找一个random指针，都必须遍历一次链表。时间复杂度O(n^2)。

可能也有人可能会想到时间换空间的方法，用hash把时间复杂度降到O(n)。

当然，还有更省时省空间的方法。

大概思路就是，在原链表的基础上，把每一个节点复制一份加的原来节点的后面，然后设置好新节点random指针，在把全部的新节点从原链表中分离出来。构成一个新链表，这个链表就是我们要的原链表的拷贝。

以下有三个函数，第一个明显就是复制新节点并把其增加到被复制节点的后面。第二个。由于新节点的random指针还是指向旧节点的。要把它指向新节点。非常easy，由于每一个节点的新节点都是在原来的节点之后的。

第三个函数。把新节点从原链表中抽离，构成一个新链表。

这样的方法的优点就是。时间复杂度仅仅有O(n)，并且我们不须要额外的空间。

class Solution {

public:

    void CloneNode(RandomListNode *head) {

        RandomListNode * p = head;

        while (NULL != p) {

            RandomListNode * CloneNode = new RandomListNode(p->label);

            CloneNode->next = p->next;

            CloneNode->random = p->random;

            p->next = CloneNode;

            p = CloneNode->next;

        }

    }

    void ConnectRandomNode(RandomListNode * head) {

        RandomListNode * p = head;

        while (NULL != p) {

            RandomListNode *pclone = p->next;

            if (NULL != pclone->random) {

                pclone->random = pclone->random->next;

            }

            p = pclone->next;

        }

    }

    RandomListNode *copyRandomList(RandomListNode *head) {

        if (NULL == head)

            return head;

        CloneNode(head);

        ConnectRandomNode(head);

        RandomListNode *pnode = head;

        RandomListNode *pclonehead = pnode->next;

        RandomListNode *pclonenode = pnode->next;

        while (NULL != pnode) {

            pnode->next = pclonenode->next;

            pnode = pnode->next;

            if (NULL != pnode){

                 pclonenode->next = pnode->next;

                 pclonenode = pclonenode->next;

            }

        }

        return pclonehead;

    }

};