25.合并两个有序链表

思路：
基础题目，设置3个指针，2个分别指向2个有序链表，第3个用来拼接最后的合并链表（保存好要返回的头结点）。没什么好说的。
应用：
链表排序。对链表进行归并排序的时候，本题的算法相当于是归并排序中的merge操作。

拓展：链表排序
难点：

1. 找链表中点
2. merge操作的实现

逐个攻破：

• 先来说merge操作的实现
  有2种方式，1种是递归，1一种是循环。其中递归方便理解，但空间复杂度为O（n）（系统栈的调用）
  递归实现：

TreeNode* merge(TreeNode *a,TreeNode *b){
//定义终止条件  
if(a==nullptr)
      return b;
if(b==nullptr)
      return a;
//开始递归过程
if(a->val<=b->val){
a->next=merge(a->next,b);
reutrn a;
}  
else{
b->next=merge(a,b->next);
return b;
}
}

循环实现merge

TreeNode *merge(TreeNode *a,TreeNode *b){
//judge illegal
if(a==nullptr)
return b;
if(b==nullptr)
return a;
TreeNode *c,*head;
if(a->val<=b->val){
 c=a;
a=a->next;
}
else{
c=b;
b=b->next;
}
head=c;
while(a&&b){
if(a->val<=b->val){
c->next=a;
a=a->next;
}
else{
c->next=b;
b=b->next;
}
c=c->next;
}
c->next=nullptr;
if(a!=nullptr)
c->next=a;
if(b!=nullptr)
c->next=b;
return head;
}

可见循环的代码比递归的代码要冗余许多，但是执行效率会更高，两种实现方式都不是很难，其实就是简单的逻辑判断，判断一下是a链表的值还是b链表的值大，分别处理即可

• 找到链表中点
  采用快慢指针的方法，快指针走2步，慢指针走一步，因为要切分链表一定要明确切分的范围，否则容易犯迷糊，比如把链表切分成[head,slow],[slow->next,null]两部分或者[head,slow->prior],[slow,null]两部分，定义好切分的范围后，写代码会思路更加清晰，不容易出错。
  另外值得注意的是链表不具备随机访问的能力，因此我们需要额外设置一个指针split来标记我们的链表切分点（可以标记slow节点的前一个或者后一个节点）

逻辑代码（不推荐封装成函数，因为我们需要split和slow两个节点，封装成函数如果用cpp的话还是挺麻烦的）
find the middle point in a linkedList

vector<TreeNode *>findMP(TreeNode *head){
//judge illeagal
if(head==nullptr)
return nullptr;
TreeNode *slow=head,*fast=head,*split=head;
while(fast&&fast->next){
fast=fast->next->next;
split=slow;//mark the slow->prior
slow=slow->next;
}
return {split,slow} //[head,split],[slow,nullptr]
}

整体实现：  
目前我们已经实现了找到链表中点和merge操作，那么我们就可以用归并排序进行链表排序了。  
```cpp
TreeNode *sortList(TreeNode *head){
 //judge illeagal
if(head==nullptr||head->next==nullptr)
return head;
//find the middle point  

vector<TreeNode> split=findMP(head);
split[0]->next=nullptr;
head=sortList(head);
split[1]=sortList(split[1]);
merge(split[1]);

}

循环实现：（待补充）