个人技术分享

·人的才华就如海绵的水,没有外力的挤压,它是绝对流不出来的。流出来后,海绵才能吸收新的源泉。💓💓💓

目录

说在前面

题目一:环形链表

 题目二:环形链表 II

题目三:随机链表的复制

SUMUP结尾


说在前面

 dear朋友们大家好!💖💖💖我们又见面了,接着上一个篇目,我们接着继续练习有关链表的面试题、OJ题,希望大家和我一起学习,共同进步~

 👇👇👇

友友们!🎉🎉🎉点击这里进入力扣leetcode学习🎉🎉🎉


​以下是leetcode题库界面:

 👇👇👇

🎉🎉🎉点击这里进入牛客网NowCoder刷题学习🎉🎉🎉
​以下是NowCoder题库界面:

​​

 ​​

题目一:环形链表

题目链接:141. 环形链表 - 力扣(LeetCode)

题目描述:

题目分析:

 思路:快慢指针法。创建快慢指针fast、slow,快指针每次走两步,慢指针每次走一步,如果fast追击上slow(即fast最终等于slow),则链表带环,否则不带环。

代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    ListNode* slow = head, *fast = head;//创建快慢指针fast、slow
    while(fast && fast->next)//fast走两步,slow走一步
    {
        slow = slow->next;
        fast = fast->next->next;

        if(slow == fast)//fast追击上slow,则链表带环
            return true;
    }
    return false;
}

思考下列问题:

 当然,虽然这道题比较简单,但是有些问题我们还是需要搞清楚:

1、为什么一定会相遇,有没有可能会错过,永远追不上?请证明。

答:不会错过。

证明:

假设slow进环时,fast和slow之间的距离为d,那么在fast追击slow的过程中,距离变化为d、d-1、d-2、d-3、...、2、1、0,最终会减到0。当距离为0时,fast追上slow,也就是每追击一次距离d减小1,所以一定能追上。

2、slow一次走1步,fast走3步可以吗?4步、5步、n步呢?请证明。

答:不稳定,有可能很久都追不上。

证明:

我们先考虑slow走1步,fast走3步的情况,剩下的都是如法炮制。同样假设fast和slow之间的距离为d,那么在fast追击slow的过程中,距离变化为d、d-2、d-4、d-6、...,此时就需要讨论d的奇偶性。如果d是偶数,那么d可以减到0,即fast最终会追上slow,但是如果d是奇数,那么d不是2的倍数,它会错过slow并新的距离为C-1(假设C是环的节点数),进入新一轮的追击过程,直到他们两的距离是2的倍数,此时这一轮就可以追上了。

永远追不上的条件:同时存在C是偶数且距离d(或N)为奇数,那么就会永远追不上。 

那是否真的会有这种情况呢?我们需要寻找C和N之间的关系:

证明:

假设slow进环时,fast和slow的距离是N,带环部分的节点数为C,链表不带环部分的节点数为L,slow进环时fast已经在环中转了x圈,则有:

slow走的距离是:L

fast走的距离是:L + xC + (C - N)

由于fast走的距离是slow的三倍,则有:3L = L + xC + C - N

化简得到:2L = (x + 1)C - N

显然C为偶数且N为奇数不能同时成立,也就是说,fast最终总是会追击上slow。

 ​​

 题目二:环形链表 II

题目链接:142. 环形链表 II - 力扣(LeetCode)

题目描述:

题目分析:

 思路1:快慢指针法。用题目一中的方法找到fast追击上slow的节点,记为meet,再将head记为cur,让meet和cur同时走,它们会再第一个相交节点相遇,即入环的第一个节点。

那为什么会在第一个相交节点相遇呢?

解:

假设fast追上slow时的节点,即meet节点,逆时针距离入环的第一个节点的距离为N,不带环部分节点数为L,带环部分节点数为C,则有:

slow走的距离是:L + N(fast一次走2步,在一圈内一定能追上)

fast走的距离是:L + xC + N

又因为fast走的距离是slow的两倍,则有:2(L + N) = L + xC + N

化简得到:L = xC- N

显然随着x的变化,指针fast在环内距离入环的第一个节点的距离f(x)是一个周期函数,周期为T = 1,那么L(x)也是关于x的周期函数,周期T = 1。

所以:L = C - N(就比如sinπ、sin3π和sin5π都是相等的)

由此得到不带环部分的节点数等于meet距离入环的第一个节点的节点数相等,所以它们以相同速度移动,一定会再第一个相交节点相遇。

代码如下: 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* detectCycle(struct ListNode* head) {
    ListNode* slow = head, * fast = head;//创建快慢指针
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)//fast追上slow
        {
            ListNode* meet = slow;
            ListNode* cur = head;
            while (meet != cur)//meet和cur相遇,则为第一个相交节点
            {
                meet = meet->next;
                cur = cur->next;
            }
            return meet;
        }
    }
    return NULL;//没有相交节点则返回NULL
}

思路2:先用思路1的方法找到meet,然后将meet->next设置为newhead,然后让环断裂,使其转化为相交链表找第一个相交节点(上个篇目解析过这类题)。 

这个思路可能更好想,但是代码却要更加复杂一些。

代码如下: 

/**
 * 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* cur1 = headA, * cur2 = headB;
	int lenA = 0;
	int lenB = 0;
	while (cur1->next)//统计链表A的长度
	{
		lenA++;
		cur1 = cur1->next;
	}
	while (cur2->next)//统计链表B的长度
	{
		lenB++;
		cur2 = cur2->next;
	}
	if (cur1 != cur2)//判断是否有交点
		return NULL;
    //假设法,设置长短链表
	ListNode* LongList = headA, * ShortList = headB;
	if (lenA < lenB)
	{
		LongList = headB;
		ShortList = headA;
	}
	int gap = abs(lenA - lenB);//两链表节点差值
	while (gap--)//让长的先走差值的步数
	{
		LongList = LongList->next;
	}
	while (LongList != ShortList)//让两链表一起走,第一个相等的就是交点
	{
		LongList = LongList->next;
		ShortList = ShortList->next;
	}
	return LongList;
}
//带环链表寻找第一个相交节点
struct ListNode *detectCycle(struct ListNode *head) {
    ListNode *slow = head, *fast = head;//创建快慢指针
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
           ListNode* meet = slow;
           ListNode* newhead = meet->next;//新单链表的头
           meet->next = NULL;//尾部置为NULL
           ListNode* cur = getIntersectionNode(newhead, head);
           return cur;
        }
    }   
    return NULL;
}

第一个函数我们在上一篇目中有详细解析,这里直接CV就可以了。 虽然能够通过,但是修改了链表,本质上不符合题目要求了,但是也是个值得思考的思路。

 ​​

题目三:随机链表的复制

题目链接:138. 随机链表的复制 - 力扣(LeetCode)

题目描述:

注:深拷贝:拷贝一个值个指向和当前链表一模一样的链表。

题目分析:

 思路:快先将新的节点交错插入到原随机链表中,然后完成设置random后再将新的节点尾插到新链表newhead中。

这道题目创建节点其实不难,难就难在random是随机的,应该如何处理random的指向是这道题目的难点。我们如果错位插入,就可以得到新节点和旧链表之间的关系,那么新的节点的random指针都会指向插入了新节点的链表的random的next指针(空指针除外)。

比如,上面原来的第二个节点的random指向了第一个节点,那么新的第二个节点的random就指向第一个节点的next节点。

代码如下:

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {
    Node* cur = head;
    while (cur)//创建新节点并错位插入旧节点
    {
        Node* copy = (Node*)malloc(sizeof(Node));
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
        cur = copy->next;
    }
    cur = head;
    while (cur)//设置random指针的指向
    {
        Node* copy = cur->next;
        if (!cur->random)
            copy->random = NULL;
        else
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }
    cur = head;
    //创建新链表
    Node* newhead = (Node*)malloc(sizeof(Node));
    Node* newtail = newhead;
    while (cur)//将新节点尾插到新链表
    {
        Node* copy = cur->next;
        newtail->next = copy;
        newtail = newtail->next;
        cur->next = copy->next;//恢复原链表
        cur = copy->next;
    }
    if (newtail)
        newtail->next = NULL;
    return newhead->next;
}

这道题目不论是思路还是代码书写都很有难度,如果你看了我的讲解能够独立地写出上面代码(不一定非要和我一样),那么恭喜你,在当前阶段你的链表已经过关了!

 

SUMUP结尾

数据结构就像数学题,需要刷题才能对它有感觉。之后还会更新数据结构相关的练习题、面试题,希望大家一起学习,共同进步~

如果大家觉得有帮助,麻烦大家点点赞,如果有错误的地方也欢迎大家指出~