[LeetCode] 138.复制带随机指针的链表

本文带大家来做一道LeetCode上链表题,这道题在剑指offer这本书中同样出现过,非常值得研究的一道题

在LeetCode是138题 传送门

有很多朋友看到这么密密麻麻的题目有很头疼,觉得自己看不懂,其实细心看一下也就还好,本身表达的已经很清楚

这道题的是意思就是让你

给你一个链表,每个节点增加了一个元素, 之前不是只有val , next 么,现在加了一个random, random指向链表中的任意一个位置,或者为NULL
让你复制一个链表出来, 状态一样,如果没有这个random的话,复制一个链表不是简简单单,关键是这个random要指向新链表的相对位置

我们来分析一下思路

思路一 : 暴力算法O(N ^ 2)

相信大家肯定想的暴力算法,先复制一个新链表出来,然后去看看原来的链表节点的random指向的是第几个,
然后让新链表的也指向新链表的第几个就可以了

第一步:拷贝链表

复制链表,新的头是copyHead, 然后处理最难处理的 random,

第二步:处理random

通过原链表找相对位置, 然后让复制链表也指向对应的位置

我们来分析一下

在这里定义的变量比较多, srcCur代表找的遍历节点,copyCur自然是复制链表的遍历节点
srcTmp , copyTmp 都是从头开始往后走遍历找的节点
pos代表相对位置,你可以当做下标来理解

完整代码

struct Node* copyRandomList(struct Node* head) 
{
    if(NULL == head)
        return NULL;
    //复制新链表
    struct Node* copyHead = NULL,*copyTail = NULL;
    struct Node* cur = head;
    while(cur)
    {
        //存储cur的下一个
        struct Node* next = cur->next;
        //malloc开辟新节点
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->val = cur->val;
        //这里一定要置空
        newNode->next = NULL;
        //尾插
        if(copyHead == NULL)
        {
            //第一次尾插需要赋值
            copyHead = copyTail = newNode;
        }
        else
        {
            copyTail->next = newNode;
            //后移
            copyTail = copyTail->next;
        }
        //迭代
        cur = next;
    }
    //处理pos,找相对位置
    struct Node* srcCur = head;
    struct Node* copyCur = copyHead;
    while(srcCur)
    {
        //如果为空,那么copyCur->random = NULL;
        if(srcCur->random == NULL)
        {
            copyCur->random = NULL;
        }
        else //2.如果不为空,就去找相对位置
        {
            //用来查找的头结点,每次都从头开始
            struct Node* copyTmp = copyHead;
            struct Node* srcTmp = head;
            int pos = 0;
            //原链表找
            while(srcTmp)
            {
                if(srcTmp == srcCur->random)
                {
                    break;
                }
                pos++;
                srcTmp = srcTmp->next;
            }
            //复制链表找,
            while(pos--)
            {
                copyTmp = copyTmp->next;
            }
            //赋值
            copyCur->random = copyTmp;
        }
        srcCur = srcCur->next;
        copyCur = copyCur->next;
    }

    return copyHead;
}
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

可以看到,虽然复杂度比较高,但是还是能跑过的,时间复杂度为O(N^2) , 但是我们总是想着去找更优的算法,可不可以降低到O(N)呢,当然是可以的,我们来看思路二

思路二: 接到相邻位置

这个思路很难想到,听我细细道来,先给 大家放一个图

大家可以看一下这个图,我们把复制的节点都拼接到原来节点的后面,这个还是比较容易的,大家能不能看出复制节点的random如何找到正确正确的位置呢? ???

好, 这个思路大约有三步,

1. 复制节点,拼接到后面
2. 处理复制节点的random
3. 把节点拆出来, 然后组成新链表,恢复原链表

第一步:复制节点,拼接到后面

这个还是比较相对比较简答的,我们分析一下

第二步:处理复制节点的random

这道题的难点就在于如何处理复制节点的random, 我们来分析一下

第三步:把节点拆出来, 然后组成新链表,.恢复原链表

最难的random问题解决了,我们就来把这个链表拆出来, 组成复制链表

其实就像删除节点一样,只不过是组成新节点,还是比较简单的

这里不重新恢复原链表也能过,但是最好还是恢复一下

Code

struct Node* copyRandomList(struct Node* head) 
{
    if(NULL == head)
        return NULL;
    //复制节点,拼接到后面
    struct Node* cur = head;
    struct Node* copyHead = NULL, *copyTail = NULL;

    while(cur)
    {
        //开辟新节点
        struct Node* copyNode = (struct Node*)malloc(sizeof(struct Node));
        //调整新节点指向
        copyNode->val = cur->val;
        copyNode->next = cur->next;
        //拼接
        cur->next = copyNode;
        //迭代
        cur = copyNode->next;
    }

    //处理复制random问题
    //重置cur
    cur = head;
    while(cur)
    {
        struct Node* copyNode = cur->next;
        if(cur->random == NULL)
        {
            copyNode->random = NULL;
        }
        else
        {
            copyNode->random = cur->random->next;
        }
        //迭代
        cur = copyNode->next;
    }
    //把节点拆出来, 然后组成新链表,.恢复原链表
   
    cur = head;
    while(cur)
    {
        struct Node* copyNode = cur->next;
        if(copyHead == NULL)
        {
            copyHead = copyTail = copyNode;
        }
        else
        {
            copyTail->next = copyNode;
            copyTail = copyTail->next;
        }
        cur->next = copyNode->next;
        //迭代cur
        cur = copyNode->next;
    }
    return copyHead;
}
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
51
52
53
54
55
56
57
58
59

总结

这道题可以练习大家对于链表基础操作的掌握,很有针对性
这道题到这里就结束了,希望大家可以画图分析,自己实现,感谢收看,