数据结构 | 题目练习第二章 | 合并两个有序链表 | 环形链表 | 环形链表入环第一个节点
一、合并两个有序链表
思路一：
从头开始，取两个链表中小的那个尾插到新链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
// 首先判断链表是否为空
if(l1 == NULL){
return l2;
}
if(l2 == NULL){
return l1;
}
struct ListNode* head = NULL,*tail = NULL;
while(l1 != NULL && l2 != NULL){
// 如果l1的val小于l2的val就将l1的val尾差
if(l1->val < l2->val){
// 第一个tail是为NULL
if(tail == NULL){
head = tail = l1;
}
else{
// tail 已经有节点，连接下一个节点
tail->next = l1;
// 并且tail往后面走
tail = tail->next;
}
// 同时l1插入后到下一个节点
l1 = l1->next;
}else{ // 这里就是l2小了
if(tail == NULL){
head = tail = l2;
}
else{
tail->next = l2;
tail = tail->next;
}
l2 = l2->next;
}
}
// 不一定同时结束，判断谁还有剩余，将剩余的连接到后面
if(l1)
tail->next = l1;
if(l2)
tail->next = l2;
return head;
}
- 优化后：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* head = NULL,*tail = NULL;
// 1.首先判断链表是否为空
if(l1 == NULL){
return l2;
}
if(l2 == NULL){
return l1;
}
// 1.1可以首先取一个做头
if(l1->val < l2->val){
head = tail = l1;
l1 = l1->next;
}else{
head = tail = l2;
l2 = l2->next;
}
//1.2或者开辟一个哨兵位
// head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
// 但是注意返回值 head，需要返回第一个头，而不是哨兵位
// struct ListNode* first = head->next;
// free(head);
// return first;
while(l1 != NULL && l2 != NULL){
// 如果l1的val小于l2的val就将l1的val尾差
if(l1->val < l2->val){
tail->next = l1;
l1 = l1->next;
}else{ // 这里就是l2小了
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
// 不一定同时结束，判断谁还有剩余，将剩余的连接到后面
if(l1)
tail->next = l1;
if(l2)
tail->next = l2;
return head;
}
二、环形链表
思路一：快慢指针
其他问题：
- 请证明slow和fast一定会在环里相遇？有没有可能永远跟不上？（slow一次走一步，fast一次走两步）
答：slow进环了以后，fast正式开始追了，假设fast和slow之间的距离是N，追的过程中，他们的距离是如何变化的？
N fast追slow的过程中距离每次缩小1
N-1
N-2 距离是0的时候就相遇
- slow走一步，fast走3步行不行？slow走一步，fast走4步行不行？… 请证明
答：slow走一步，fast走3步，不一定能追上，甚至可能会死循环，永远追不上。
会出现下面两种可能性：
- 0代表相遇
- -1代表fast反超了slow，那么进入新的追逐，他们之间的距离是C-1（假设C是环的长度），
- 如果C-1是偶数就能追上，如果C-1是奇数就永远追不上；因为每次距离减少2
- 距离是奇数就意味着快追上时，距离又会是-1，然后fast反超slow，这里距离又是C-1，那么就死循环了，永远追不上。
NN N-2N-2 N-4N-4 N-6N-6 ... ... 0-1 如果N是偶数如果N是奇数
- slow走一步，fast走4步也是同理：
- 相当于是3的倍数才会为0，如果不是距离就可能是-1，-2，所以说距离只要不是3的倍数就追不上。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struc t ListNode *head) {
struct ListNode* slow = head,*fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
// 如果相遇就返回true
if(slow == fast){
return true;
}
}
// 如果循环完毕，还没有等于就没有带环
return false;
}
三、环形链表2
思路：一个指针从meet点开始走，一个指针从链表起始点走，他们会在入口点相遇
推导过程：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow = head,*fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
// 推导的结论:一个指针从相遇点meet开始走，一个指针从head走，他们会在入口点相遇
if(slow == fast){
struct ListNode* meet = slow;
while(head != meet){
// 他们没有相等则继续往下走
head = head->next;
meet = meet->next;
}
// 退出循环则相遇
return meet;
}
}
// 表示无环等于空
return NULL;
}
原文地址：https://blog.csdn.net/ZJC744575/article/details/143470794
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！