题目
请实现一个函数可以复制一个复杂链表。
在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。
注意：
函数结束后原链表要与输入时保持一致。

解法：模拟

首先，在每个结点后面复制一份同样的结点
然后遍历整张链表的奇数位置（原始）结点，如果有random，那么复制，即 p->next->random = p->random->next
最后，将整张链表按奇数位置和偶数位置分开成两张链表
时间复杂度O(n)，空间复杂度O(1)

/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        for (auto p = head; p;) {
            auto copy = new ListNode(p->val);
            auto next = p->next;
            p->next = copy;
            copy->next = next;
            p = next;
        }
        for (auto p = head; p; p = p->next->next) {
            if (p->random) {
                p->next->random = p->random->next;
            }
        }
        auto dummy = new ListNode(-1);
        auto cur = dummy;
        for (auto p = head; p; p = p->next) {
            cur->next = p->next;
            cur = cur->next;
            p->next = p->next->next;
        }
        return dummy->next;
    }
};