qq是哪一个软件公司开发的_证书查询入口官网_网站seo排名优化工具在线_百度网址导航

一、合并两个有序链表

21. 合并两个有序链表

思路一：

从头开始，取两个链表中小的那个尾插到新链表

/*** 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是为NULLif(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;
}

二、环形链表

141. 环形链表

思路一：快慢指针

其他问题：

1. 请证明slow和fast一定会在环里相遇？有没有可能永远跟不上？（slow一次走一步，fast一次走两步）

答：slow进环了以后，fast正式开始追了，假设fast和slow之间的距离是N，追的过程中，他们的距离是如何变化的？

N fast追slow的过程中距离每次缩小1

N-1

N-2 距离是0的时候就相遇

1. 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，那么就死循环了，永远追不上。

N									N
N-2									N-2
N-4									N-4
N-6									N-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;// 如果相遇就返回trueif(slow == fast){return true;}}// 如果循环完毕，还没有等于就没有带环return false;
}

三、环形链表2

142. 环形链表 II

思路：一个指针从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;
}