C学习（数据结构）--＞单链表习题

目录

一、环形链表

题一：环形链表

思路：

思考一：为什么？

思考二：快指针一次走3步、4步、......n步，能否相遇

step1：

step2：

代码：

题二： 环形链表 II

思路：

思考：为什么？

代码：

二、随机链表的复制

思路：

步骤一：

步骤二：新结点的随机指向结点

步骤三：链接新结点

代码： 

---

一、环形链表

题一：环形链表

https://leetcode.cn/problems/linked-list-cycle/description/

思路：

使用快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表的头结点往下走，则一定会在环形链表的环中相遇。

思考一：为什么？

设慢指针为 slow ，快指针为 fast ，头结点到入环点的长度为 L，环的长度为 C ，则当 slow 到达入环点时，从 fast 到达 slow 的长度为 N ，则

slow 到达入环点后 slow 和 fast 在环内行走，则

此时变为追击问题，快指针一次走两步，慢指针一次走一步，没走一步，快慢指针之间的距离减一，即：N，N-1，N-2，N-3......3，2，1，0，两指针相遇。

思考二：快指针一次走3步、4步、......n步，能否相遇

step1：

当快指针一次走三步时，每走一步，两指针之间的距离缩小两步，此时分为两种情况

• N为偶数：N，N-2，N-4，N-6，......4，2，0（两指针相遇 ）
• N为奇数：N，N-2，N-4，N-6，......3，1，-1（两指针错开，进入新一轮追击，此时，两指针之间的距离变为 C +（-1）== C-1 ）

此时若 C-1也分两种亲情况

• C-1为偶数，则 C-1 类似于 N为偶数，两指针相遇
• C-1为奇数，则 C-1 类似于 N为奇数，两指针错开，那么两者便一直不会相遇

总结：当N为奇数，C为偶数时，两指针 有可能 不会相遇

step2：

还是这张图，当 slow 到达入环点时，假设 fast 已经走了x*C圈，则从中可以得到两指针所走的路程

• fast：L+x*C+（C-N）
• slow：L

又因为慢指针一次走一步，快指针一次三步，由此可以得出方程式

3*S（slow）= S（fast） <-----> 3*L = L+x*C+（C-N）<----->  2*L= (x+1)*C-N

因为 2*L 一定为偶数，这满足方程式的情况有两种

• 偶数 = 偶数 - 偶数
• 偶数 = 奇数 - 奇数

因此当 N 为偶数时，(x+1)*C一定为偶数，即 C 为偶数；当 N 为奇数时，(x+1)*C一定为奇数，即 C 为奇数，不存在step1中 N为奇数，C为偶数 的情况，则两指针一定会相遇。快指针一次走4、5、......n步同样如此证明。

结论：快指针一次不管走多少步都一定会与慢指针相遇

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode LN;
bool hasCycle(struct ListNode *head) {LN* slow,*fast;slow = fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){return true;}}return false;
}

题二： 环形链表 II

https://leetcode.cn/problems/linked-list-cycle-ii/description/

思路：

让一个指针从头结点开始遍历链表，同时让一个指针从 判定该链表为环形链表的相遇点开始绕环运行，两个指针都是每次只走一步，最终一定会在入口点相遇

思考：为什么？

设头结点为 H ，入环点为 E ，H 到 M 的距离为 L，快慢指针相遇点为 M  ，E 到 M 的距离为 X ，环的长度为 R 则

 则快慢指针相遇时，快（fast）慢（slow）指针相遇时，假设快指针已经绕环走了 n 圈，则，两指针走过的路程

• fast ：L+X+n*R
• slow：L+X

取快指针一次两步，慢指针一次一步，可得方程式

L+X+n*R = L+X 

化简得 L = n*R-X；

即 L= (n -1)*R+(R-X)，n取1，2，3，4......

当n = 1时，L = R-X，则

则 让一个指针从头结点开始遍历链表，同时让一个指针从 判定该链表为环形链表的相遇点开始绕环运行，两个指针都是每次只走一步，最终一定会在入口点相遇、

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode LN;
struct ListNode *detectCycle(struct ListNode *head) {LN* slow,*fast;slow = fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){slow = head;while(slow != fast){slow = slow->next;fast = fast->next;}return slow;}}return false;
}

二、随机链表的复制

https://leetcode.cn/problems/copy-list-with-random-pointer/description/

思路：

步骤一：

遍历原链表根据结点保存的数据，申请并复制到新的结点，并且插入到该节点后。

步骤二：新结点的随机指向结点

赋值 ：新结点的随机指向结点 = 原链表结点的随机指向结点的下一个结点

 

步骤三：链接新结点

 

代码： 

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/
typedef struct Node Node;
//申请新结点
Node* BuyNode(int val)
{Node* newNode = (Node*)malloc(sizeof(Node));newNode->val = val;newNode->next = NULL;newNode->random = NULL;return newNode;
}
//插入原链表
void PushNode(Node* pNode)
{Node* pcur = pNode;while(pcur){Node* pNext = pcur->next;Node* newNode = BuyNode(pcur->val);newNode->next = pNext;pcur->next = newNode;pcur = pNext;}
}
struct Node* copyRandomList(struct Node* head) {if(head == NULL){return head;}//插入原链表PushNode(head);//拷贝randomNode* pcur = head;while(pcur){Node* pcpy = pcur->next;if(pcur->random != NULL){pcpy->random = pcur->random->next;}pcur = pcpy->next;}//链接新链表Node *newHead,*newTail;pcur = head;newHead = newTail = pcur->next;while(pcur->next->next){pcur = pcur->next->next;newTail->next = pcur->next;newTail = pcur->next;} return newHead;
}