【LeetCode&数据结构】单链表的应用——随机链表的复制问题、相交链表问题详解-EW帮帮网

🔥个人主页：艾莉丝努力练剑

❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题

🍉学习方向：C/C++方向

⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平

前言：牛客网和LeetCode的刷题都不可或缺，我们都要做一做，无论是参加竞赛还是笔试面试，至少能提升你的代码能力！洛谷的题目也可以去做一做。力扣的题目对提升代码能力很有帮助，需要有一点基础，几乎都是接口型的题目，关于接口型和IO型的区别我们在本专栏的第一篇【LeetCode】力扣题——轮转数组、消失的数字、数组串联中就介绍过了，这里不再赘述，我们进入今天的力扣题目介绍——

正文

一、随机链表的复制问题

138.随机链表复制

博主题解链接：原链表基础上拷贝节点、置random指针、断开新旧链表解决随机链表的复制

推荐大家可以直接去看博主在力扣上面写的题解，博主介绍的还是比较详细的。

题目描述：

题目示例和提示——

1、思路

我们的思路是：原链表基础上拷贝节点、置random指针、断开新旧链表。

我们先来看看题目描述——

题目提到了深拷贝，什么是深拷贝？

（1）深拷贝

如图——

（2）浅拷贝：值拷贝

如图——

（3）深拷贝和浅拷贝的关系

2、解题过程

像这种题目拿到手我们首先就是想到要画图，一定要有这个意识，数据结构的算法题一定要画图。

如下图所示——

random如何设置？

至于为什么不这么做的理由我已经在图中标注了。

3、改进方案

我们如果创建新链表再设置random指针，不太好去改变，所以我们可以三步走：

（1）在原链表基础上拷贝节点

（2）置random指针

（3）断开新旧链表

变成这样——

这里我们通过示例1看看，random表示从0开始的下标——

我们测试一下，代码演示——

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;
Node* buyNode(int x) 
{
	Node* newnode = (Node*)malloc(sizeof(Node));
    newnode->val = x;
    newnode->next = newnode->random = NULL;

    return newnode;
}

void AddNode(Node* head)
{
    Node* pcur = head;
    while(pcur)
    {
        Node* newnode = buyNode(pcur->val);
        Node* next = pcur->next;
        newnode->next = next;
        pcur->next = newnode;
        pcur = next;
    }
}

void setRandom(Node* head)
{
    Node* pcur = head;
    while(pcur)
    {
        Node* copy = pcur->next;
        if(pcur->random)
            copy->random = pcur->random->next;
            pcur = copy->next;
    }
}
struct Node* copyRandomList(struct Node* head)
{
    //在原链表基础上拷贝节点并且插入在原链表中
    AddNode(head);
    //设置random
    setRandom(head);
    //断开新链表
    Node* pcur = head;
    Node* copyHead,*copyTail;
    copyHead = copyTail = pcur->next;
    while(copyTail->next)
    {
        pcur = copyTail->next;
        copyTail->next = pcur->next;
        copyTail = copyTail->next;
    }
    return copyHead;
}

运行一下——报错了！

我们判断一下头节点是否为空，是就直接返回head——

4、代码演示：

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;
Node* buyNode(int x) 
{
	Node* newnode = (Node*)malloc(sizeof(Node));
    newnode->val = x;
    newnode->next = newnode->random = NULL;

    return newnode;
}

void AddNode(Node* head)
{
    Node* pcur = head;
    while(pcur)
    {
        Node* newnode = buyNode(pcur->val);
        Node* next = pcur->next;
        newnode->next = next;
        pcur->next = newnode;
        pcur = next;
    }
}

void setRandom(Node* head)
{
    Node* pcur = head;
    while(pcur)
    {
        Node* copy = pcur->next;
        if(pcur->random)
            copy->random = pcur->random->next;
            pcur = copy->next;
    }
}
struct Node* copyRandomList(struct Node* head)
{
    if(head == NULL)
    {
        return head;
    }
    //在原链表基础上拷贝节点并且插入在原链表中
    AddNode(head);
    //设置random
    setRandom(head);
    //断开新链表
    Node* pcur = head;
    Node* copyHead,*copyTail;
    copyHead = copyTail = pcur->next;
    while(copyTail->next)
    {
        pcur = copyTail->next;
        copyTail->next = pcur->next;
        copyTail = copyTail->next;
    }
    return copyHead;
}

复杂度：时间复杂度：O(N)，空间复杂度：O(1)。

运行一下，通过了。

二、相交链表问题

160.相交链表

博主题解链接：利用长度差求解相交链表

推荐大家可以直接去看博主在力扣上面写的题解，博主介绍的还是比较详细的。

题目描述：

我们来看题目给的几个示例——

本题也给了一个提示——

1、思路

从链表的长度我们可以联想到A和B存在长度差。

因此我们的思路是：求两个链表的长度，先让长链表走长度差（比如我们设为val，设什么都可以）步，长短链表再开始同步遍历，找相同的节点。

2、解题过程

像这种题目拿到手我们首先就是想到要画图，一定要有这个意识，数据结构的算法题一定要画图。

两个链表相交有哪几种情况？如下图所示——

如何判断链表是否相交？

两个链表的尾节点相同，两个链表一点相交

接下来我们就可以写代码了——

值得注意的是：

（1）链表开始往后走的时候，我们要计算A链表的长度，所以我们还得要两个计数器，定义计数器的目的也是计算每个链表里面节点的个数。

（2）int gap = abs(sizeA - sizeB);

//abs()——求绝对值——C语言库里面提供的库方法。

（3）这里shortList、longList在同一起跑线上了，while(shortList)或者用while(longList)都是一样的，这里判断如果是，两个链表就相交了。

代码演示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //求链表的长度
    ListNode* pa = headA;
    ListNode* pb = headB;
    //开始往后走的时候，我们要计算A链表的长度，所以我们还得要两个计数器
    //定义计数器，计算每个链表里面节点的个数
    int sizeA = 0,sizeB = 0;
    while(pa)
    {
        sizeA++;
        pa = pa->next;
    }
    while(pb)
    {
        sizeB++;
        pb = pb->next;
    }
    //求长度差
    int gap = abs(sizeA - sizeB);//求绝对值——C语言库里面提供的库方法
    //定义长短链表
    ListNode* shortList = headA;
    ListNode* longList = headB;
    if(sizeA > sizeB)
    {
        longList = headA;
        shortList = headB;
    }
    //让长链表先走gap
    while(gap--)//比如1
    {
        longList = longList->next;
    }
    //shortList longList在同一起跑线
    //这里如果是，就相交了
    while(shortList) //或者用while(longList)
    {
        if(shortList == longList)
        {
            return shortList;
        }
        shortList = shortList->next;
        longList = longList->next;
    }
    //链表不相交
    return NULL;
}

复杂度：时间复杂度：O(N)，空间复杂度：O(1)。

虽然有循环，但都是并列的关系，没有嵌套，时间复杂度O(N)。