题目描述

blablabla

样例

/**
 * 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) {
        if (!head) return nullptr;
        ListNode *m_head = head;
        while (head)
        {
            ListNode *next = head->next;
            head->next = new ListNode(head->val);
            head->next->next = next;
            head = head->next->next;
        }

        head = m_head;
        while (head)
        {
            if (head->random) head->next->random = head->random->next;
            head = head->next->next;

        }

        auto dummy = new ListNode(-1);
        auto dummy_head = dummy;

        while (m_head)
        {
            auto next = m_head->next->next;
            dummy->next = m_head->next;
            dummy = dummy->next;
            m_head->next = next;
            m_head = next;

        }

        return dummy_head->next;
    }
};

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla