AcWing 48. 复杂链表的复刻
宋标 Lv5
  2022-08-18 02:31:02 2022-08-18 02:31    

题目

请实现一个函数可以复制一个复杂链表。

在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。

注意：

  • 函数结束后原链表要与输入时保持一致。

数据范围

链表长度 。

题解

空间O(1), 时间O(n^2)
比较容易想到的, 时间复杂度 500*500 + 500, 可ac本题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * 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 *ans, *ans_h, *t;

        t = head;
        ans_h = ans = new ListNode(t -> val);

        while (t && t -> next)
        {
            t = t -> next;
            ans -> next = new ListNode(t -> val);
            ans = ans -> next;
        }

        t = head;
        ans = ans_h;

        while (t)
        {
            auto* random = t -> random;
            if (random)
            {
                auto *temp = head, *ans_t = ans_h;
                while (temp != random) 
                {
                    temp = temp -> next;
                    ans_t = ans_t -> next;
                }
                ans -> random = ans_t;
            }
            t = t -> next; ans = ans -> next;
        }

        return ans_h;
    }
};

空间O(n), 时间O(n)
思路很有启发性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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;

        unordered_map<ListNode*, ListNode*> map;

        map[NULL] = NULL;
        // 将新链表与旧链表映射
        for (auto p = head; p; p = p -> next)
            map[p] = new ListNode(p -> val);

        for (auto p = head; p; p = p -> next)
        {
            // 这里的思路很有启发性
            map[p] -> next = map[p -> next];
            map[p] -> random = map[p -> random];
        }

        return map[head];
    }
};

空间O(1), 时间O(n)
思路很牛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * 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;

        auto *t = head;

        // 在当前结点后复制插入一个结点
        while (t)
        {
            auto *n = new ListNode(t -> val);
            n -> next = t -> next;
            t -> next = n;
            t = n -> next;
        }

        // 复制出来的random是原random的next
        t = head;
        while (t)
        {
            if (t -> random)
                t -> next -> random = t -> random -> next;
            t = t -> next -> next;
        }

        // 分离链表
        ListNode *ans, *ans_h;
        ans_h = ans;
        t = head;

        while (t)
        {
            ans -> next = t -> next;
            ans = ans -> next;
            t -> next = ans -> next;
            t = t -> next;
        }

        return ans_h -> next;
    }
};
 评论