作者：一个喜欢猫咪的的程序员
专栏：《Leetcode》
喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
目录
21.合并两个有序链表
21. 合并两个有序链表
https://leetcode.cn/problems/merge-two-sorted-lists/
题目描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
题目描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
思路：
思路一： 迭代法：
将两个链表的元素做对比，哪个比较小哪个下来，当tail还为NULL时，需要将list1or list2赋值给他，再者需要注意当其中一个链表比较完了，另外一个有剩余的时候，需要将它剩余链表赋给tail
时间复杂度：O（n+m） 空间复杂度：O(1)
思路二：递归法：
现实中我们也很经常见过递归：比如：
言归正传（滑稽）
递归调用函数的过程：当我们比较两个链表的值谁小，就让改链表位置向后走，当链表位置为NULL，返回另外一个链表的位置。
递归返回过程：与调用过程相反，谁大链接谁！
时间复杂度：O(n + m) 空间复杂度：O(n+m)
代码实现：
思路一：迭代法：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ if(list1==NULL) return list2; if(list2==NULL) return list1; struct ListNode*tail,*newhead; tail=newhead=NULL; while(list1&&list2) { if(list1->val<list2->val) { if(tail==NULL) { newhead=tail=list1; } else { tail->next=list1; tail=tail->next; } list1=list1->next; } else { if(tail==NULL) { newhead=tail=list2; } else { tail->next=list2; tail=tail->next; } list2=list2->next; } } if(list1) tail->next=list1; if(list2) tail->next=list2; return newhead; }
思路二：递归法：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ if(list1==NULL) return list2; if(list2==NULL) return list1; if(list1->val<=list2->val) { list1->next=mergeTwoLists(list1->next,list2); return list1; } else { list2->next=mergeTwoLists(list1,list2->next); return list2; } }
876. 链表的中间结点
876. 链表的中间结点
https://leetcode.cn/problems/middle-of-the-linked-list/
题目描述：
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例：
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
思路：双指针思路
利用两个指针，当left走一步，right走两步，这样当left走到一半时，right刚好走完了。
时间复杂度：O（N） 空间复杂度：O（1）
代码实现：
struct ListNode* middleNode(struct ListNode* head) { if (head->next == NULL) { return head; } struct ListNode* left = head; struct ListNode* right = head; struct ListNode* ans = head; while (right != NULL && right->next != NULL) { left = left->next; right = right->next->next; } ans = left; return ans; }//876. 链表的中间结点
链表中倒数第k个结点(牛客）:
链表中倒数第k个结点_牛客题霸_牛客网
【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力
https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a
题目描述：
输入一个链表，输出该链表中倒数第k个结点。
示例：
思路：
思路一：双指针法
我们利用两个指针，当一个指针right先走k步时，left和right的间距就是k个，当right走到NULL的位置，left刚好到倒数k个的位置。当k的个数大于链表的长度时，即：当先走k步时right==NULL，直接返回NULL，
时间复杂度;O（N） 空间复杂度:O（1）
代码实现：
思路一：双指针法
truct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode*left=pListHead; struct ListNode*right=pListHead; for(int i=0;i<k;i++) { if(right==NULL) return NULL; right=right->next; } while(right) { left=left->next; right=right->next; } return left; }
