过程
迭代过程中需要三个指针：
-
p用来指向当前待处理的结点 -
lastp指向上一个处理完的结点，初始为空。这样的话，旧链表首结点就是新链表尾结点，尾结点后会自动填充NULL指针。 -
nextp指向p的下一个结点。
例如：当前需要处理2号结点
-
分配nextp
-
反转p和lastp之间的链接
-
更新lastp
-
更新p
有趣的是，三者赋值的代码首尾相接：
ListNode* nextp=p->next;
p->next=plast;
plast=p;
p=nextp;
循环终止条件
需要注意的是，在处理最后一个结点的时候，因为我们需要保留最后一个结点作为新链表的头部，所以一定是while(p->next)而非while(p)。前者终止时条件触发，p指向最后一个结点；后者终止时p为空。
此时，最后一个结点的反转需要额外完成。
CODE
ListNode* inverse(ListNode* head) {
//一个表示当前待处理的结点；一个是上次已经处理的结点
ListNode* p=head,*plast=nullptr;
//初始为null是基于最后结点的next是null的规定
//第一个结点反转后就是最后的结点，next应该为null
//循环终止条件：如果是while(p)那么循环结束时p为空，旧链表的尾部即新链表的头部就丢失了，所以一定要是while(p->next)此时p指向尾结点
while(p->next){
//预先保留p的next指针域，因为会被后面的冲掉
ListNode* nex=p->next;
//完成链接的反转
p->next=plast;
//注意以下两句的顺序
plast=p;
p=nex;
}
//记住，循环结束时，p指向尾结点，它和plast还需要反转其链接。
p->next=plast;
head=p;
return head;
}
反转链表的特定部分
将链表123456反转中间的345号结点，使得最终顺序为125436
为了便于后续操作，我们建立了一个逆序函数：
CODE
ListNode* reverL(ListNode* h,ListNode* tnext){
ListNode* p=h,*lastp=nullptr,*nextp;
while(p->next!=tnext){
nextp=p->next;
p->next=lastp;
lastp=p;
p=nextp;
}
p->next=lastp;
return p;
}
该函数加入了一个参数：tnext表示待反转部分中，最后结点的下一个位置。这样做可以把该参数设置为NULL来反转整个链表。返回新链表的首指针。
注意：整个过程仅仅是改变了结点的指针域，原来的h和tnext指针依旧有效。
K逆序
有一个单链表，请设计一个算法，使得每K个节点之间逆序，如果最后不够K个节点一组，则不调整最后几个节点。例如链表1->2->3->4->5->6->7->8->null，K=3这个例子。调整后为，3->2->1->6->5->4->7->8->null。因为K==3，所以每三个节点之间逆序，但其中的7，8不调整，因为只有两个节点不够一组。
这个结构就像一段一段接起来晒的香肠一样，处理方式也不复杂，简单来说就是从头开始数，数够K个结点，把这K个结点反转。直到遍历至尾，整个过程中记得用一个变量保存上一次处理完的部分尾结点，便于拼接。
CODE
ListNode* inverse(ListNode* head, int k) {
if(!head || k<=1 )
return nullptr;
//使用带头结点的链表，会省很多麻烦
ListNode *H=new ListNode(0);//记得删除
H->next=head;
//tail用来遍历，last记录上一个处理完的区段末尾，初始为H
ListNode *last=H,*tail=head;
int cnt=0;
while(tail){
cnt++;
if(cnt!=k){
tail=tail->next;
}else{
ListNode* tnext=tail->next,*h=last->next;
ListNode* newh=reverL(last->next,tnext);
//被处理区段的前后串接
h->next=tnext;
last->next=newh;
//更新last和tail
last=h;
tail=tnext;
cnt=0;
}
}
ListNode* u=H->next;
delete H;
return u;
}
