空间复杂度O(1)、时间复杂度O(nlogn)排序链表：代码如下所示，head为null返回head，批量声明指针变量的写法ListNode *cur, *dummy, *p, *q;（C++学了5年，今天我才知道指针的这种写法，以前因为"ListNode *cur, p=NULL, q=NULL"的报错，只会写一行一个指针变量，我把ListNode*看作一个整体了，好，大脑升级，变量类型名后面声明的变量是普通变量还是指针还是引用看变量名前面有无“*”、“&”标志来暗示），统计链表的长度n，将链表以1，2，4.。。为分组大小比较排序前后两个分组，直到整条链表，两个分组排序完两个分组中的最大值节点指向下一对分组的开始节点
ListNode* sortList(ListNode* head) {
if(head==nullptr)return head;
int n=1;
ListNode* cur=head, *dummy=new ListNode(-1, head), *p, *q;
while((cur=cur->next))n++;
for(int i=1; i<=n; i*=2){
cur=dummy;
for(int j=1; j+i<=n; j+=i*2){
p=cur->next, q=p;
for(int k=0; k<i; k++)q=q->next;
int x=0, y=0;
while(x<i&&y<i&&p&&q){
if(p->val<=q->val)cur=cur->next=p,p=p->next,x++;
else cur=cur->next=q, q=q->next,y++;
}
while(x<i&&p)cur=cur->next=p,p=p->next,x++;
while(y<i&&q)cur=cur->next=q,q=q->next,y++;
cur->next=q;
}
}
return dummy->next;
}
k个一组反转链表。以一段链表的头节点和尾节点为输入反转这段链表，p=head,tn=tail->next,while(tn!=tail){n=p->next;p->next=tn;tn=p;p=n;}。实现k个一组反转链表的伪代码：yummy=new ListNode(0,head),p=yummy,tail=yummy;while(head){for(int i=0; i<k;i++){tail=tail->next;if(!tail)return yummy->next;}tn=tail->next;tie(head,tail)=reverse(head,tail);p->next=head;head=tn;tail->next=tn;p=tail;}return yummy->next;两个一组反转链表，抓住每段链表头和尾head、head->next是互换后的tail和head这个要点
判断一个链表是否回文。一，快慢指针找到中点，循环条件!fast->next&&!fast->next->next，当fast将近到达链表的尾部，slow指针指的就是中点位置。二，反转后半部分链表的好处，反转时尾节点的next是null，一次反转后slow指针的节点在链表末尾，无论链表的长度是奇是偶，以链表的前半部分为比较基准，得出结果。
参考链接：排序链表
25. K 个一组翻转链表
24. 两两交换链表中的节点
234. 回文链表