下述题目来自微软，经改编而来。

原始题目:一个单链表的头结点，一个整数K，要求把每K个结点逆转一下，最后返回给用户逆转以后链表的头结点的指针。

“此文内容来源于=>中国大学MOOC=>数据结构(浙江大学:陈越、何钦铭)”

“https://www.icourse163.org/learn/ZJU-93001#/learn/content”

抽象链表

第一行:

单链表头结点的位置:00100(头指针,第一个元素在下述数组中的位置)

单链表需要逆转的结点个数K:4

单链表的结点数:6

后面几行:

单链表实际的结点元素。

这里整个模拟一个真实的链表，在内存里实际的状态。

开一个充分大的结构数组，来代表内存空间。

每一列:

第一行:当前结点的地址(结点所处的位置,这里是数组下标,整数来表示)

第二行:当前结点的元素

第三行:当前结点的指向下一个结点的所存位置(指向NULL,下一个是-1,标识此链表结束)

从头结点开始,顺着next指针走一圈,就可以遍历整个链表,就可以建立起下述单链表。

逆转 (单) 链表算法过程

此链表最前面，依据个人习惯，自定义加了头结点，虽然说在一定程度上浪费了空间，但是如果这个头结点的空间对自己不是特别紧要的话，那么加一个头结点，会使后面的很多操作变得比较简单。

逆序链表结果:前面1-4的四个结点，从4依次指向1，逆转链表头结点要指向4位置，1指向剩余未逆转的链表部分5位置。

注:下述每张图中的第一个链表是接的上张图中最后一次链表改造的内容，仅为了对比。

注:下述每张图中的逆序链表仅作为对比使用。

============实现方式:

前提条件:

第1个指针:new。逆转链表头结点要指向的位置，初始化的时候，显然可以指向第一个结点，可认为第一个结点是已经逆转好了的。

第2个指针:old。指向当前还没有完成逆转的老链表。

第3个指针:tmp。要做的事情是要把2的指针逆转过来指向1，但是在做此操作之前，要先把3这个位置记住，否则2指针转向，2后面的这段链表就被丢掉了，此操作要非常小心，记住3的位置之后，就可以把2的指针反向，让它指向1，完成这步之后，就可以把指针向前位移。

开始:

1)2指针反向指向1

2)NEW从1指向当前逆转链表的头结点2

3)OLD从2指向当前还没有逆转链表的头结点3

4)TMP从3指向下一个结点4

5)OLD从3反转指向新的逆转链表头结点2

继续往前:

1)以此类推，一直要重复K步。

2)实际上需要一个计数器，当需要逆转的结点个数达到了要求的K后，就可以停下来了。

最后:

1)1指针指向5(5是当前还没有逆转的老链表的头结点)。

2)第一个自定义添加的头结点指向NEW指针4位置。

3)此时完成了一个单链表的逆转操作。

逆转(单)链表算法源码

/*
逆转链表伪代码:单链表逆转的标准模板
head:在原链表中自定义添加空的头结点.
K:逆转结点数.
*/
Ptr Reverse(Ptr head, int K){
/*
计数器CNT
*/
	cnt = 1;
/*
head指针默认指向自定义添加的空头结点位置;
new指向head的next结点位置(初始化指向1,逆转链表头结点要指向的位置,可认为第一个结点是已经逆转好了的);
old指向new的next结点位置(还没有逆转的链表头结点位置);
tmp指向old的next结点位置(用于记住当old指针反向时,不会丢掉old后的链表);
*/
	newNode = head->next;
	oldNode = newNode->next;
/*
如果没有每K个逆序要求,而是要求把整个链表逆序的话,while何时结束?
剩下链表已经没有了,就可以跳出循环.
当整数K被传进来,需要计数器CNT,当CNT<K,继续做逆转,否则跳转循环返回.
每当完成一次折返,CNT++.
*/
	while(cnt < K){
		tmp = oldNode->next;
		oldNode->next = newNode;
		newNode = oldNode;
		oldNode = tmp;
		cnt++;
	}
	head->next->next = oldNode;
	//逆转后的链表头指针结点
	return newNode;
}

引发问题

问题:PAT系统是黑盒测试，有取巧方法，不管程序咋写，只要最后结果对就可以，于是大家脑洞大开，啥方法都会写出来。

比如，用顺序表存储，直接用一个数组把这些结点一个挨着一个存放，先做一个排序，然后就直接每K个结点逆序输出。

再比如，建一个堆栈，排序完成后，先每K个结点push到一个堆栈中，然后再把其一个个的弹出来输出，这样输出就是逆序的。

出题目的:学会如何真正的去逆转一个单链表，可更真实的模拟一下内存。

比如，并不是所有的结点都在一个链表上，内存空间中是有很多没用的结点的，其他程序要用的数据，在逆转时，总不能把内存空间中的所有结点都排下去，再来逆序输出，是不可能的，所以直接用取巧方法是合适的。

测试数据与边界测试

为什么提交到PAT不对？可能因为是自身的测试数据太弱了。

边界测试:

所有数据中最重要的一部分就是边界测试。

边界:比如给了一个数据范围，那么就一定要取到此范围的上界和下界。

为什么要做边界测试？

因为程序最容易出错的地方在于边边角角的地方，所以在测试程序时，一定要注意自身的边界测试是否完善。