1.寻找链表的中间节点
题目链接：876. 链表的中间结点 - 力扣（LeetCode）
我们来直接介绍一个思路：快慢指针
快慢指针是指我们创建创建2个指针，一个为快指针，一个为慢指针，且快指针一次走的步数是慢指针的两倍。两个指针同时往后走，当快指针为空或者快指针->next为空时，此时，慢指针的位置恰好是中间节点。
1.1 节点的个数为奇数
上图为了方便理解，画了两条链表。其实两个指针是在一条链表里面实现的。
节点个数为奇数时，当fast指针走到节点末尾时，slow指针指针的位置恰好是节点的中间位置。
1.2 节点的个数为偶数
当节点的个数为偶数时，当fast指针最后为空指针时，slow指针的位置恰好是节点的中间节点。
代码实现
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode*slow=head;ListNode*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;
}注意事项：循环条件不能写成while(fast->next&&fast)，因为当链表的节点个数为偶数个时，fast指针最终会为空指针，则fast->next就会报错，如果按照我上面那样写，当fast为空时，循环条件的表达式就会短路，不会执行后面的fast->next。
2.合并两个有序链表
做题链接：21. 合并两个有序链表 - 力扣（LeetCode）
暴力解题思路：直接创建一个新链表，两个链表之间各个节点的数据依次进行比较，数据小的插入新链表。
如上面的过程图所示，数据小对应的节点被拿出来插入新的节点，接着让对应的节点向后走到下一个节点，直到有一条链表走完。
代码实现
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1==NULL){return list2;}if(list2==NULL){return list1;}//创建新链表ListNode*newhead,*newtail;newhead=newtail=NULL;//遍历原链表ListNode*l1=list1;ListNode*l2=list2;while(l1&&l2){if(l1->val<l2->val){if(newhead==NULL){newhead=newtail=l1;}else{newtail->next=l1;newtail=l1;}l1=l1->next;}else{if(newhead==NULL){newhead=newtail=l2;}else{newtail->next=l2;newtail=l2;}l2=l2->next;}}if(l1){newtail->next=l1;}if(l2){newtail->next=l2;}return newhead;
}
当写完代码我们发现，如上图，有两段一样的代码，这就造成了代码的拥挤，造成有这两段带码的原因：因为新建的头节点和尾节点存在空指针的情况，需要就行判空。
解决方法：建立哨兵位，让哨兵位作为新的头节点，并且哨兵位不存放任何数据。
优化代码
#include<stdlib.h>typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1==NULL){return list2;}if(list2==NULL){return list1;}//建立哨兵位ListNode*newhead,*newtail;newhead=newtail=(ListNode*)malloc(sizeof(ListNode));//遍历原链表ListNode*l1=list1;ListNode*l2=list2;while(l1&&l2){if(l1->val<l2->val){newtail->next=l1;newtail=l1;l1=l1->next;}else{newtail->next=l2;newtail=l2;l2=l2->next;}}if(l1){newtail->next=l1;}if(l2){newtail->next=l2;}ListNode*next=newhead->next;free(newhead);newhead=NULL;return next;
}注意事项：使用malloc函数，最后要记得销毁掉，不然可能会造成内存溢出。
我们要返回的节点是哨兵位的下一个节点，因为返回前要将哨兵位销毁掉，所以我们要提前将哨兵位的下一个节点存储起来。
