本文主要是介绍MOOC 数据结构 | 2. 线性结构（6）：习题选讲---Reversing Linked List，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
02-线性结构3 Reversing Linked List (25 分)
Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.
Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤105) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
Then N lines follow, each describes a node in the format:
Address Data Next
where Address is the position of the node, Data is an integer, and Next is the position of the next node.
Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
Sample Output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1分析
什么是抽象的链表
- 有块地方存数据
- 有块地方存指针 ---- 下一个结点的地址
样例输入可以模拟一个真实的链表在内存里存在状态，开一个结构数组来代表内存空间，样例输入中的位置就是在数组中的下标，指针其实就是一个整数，记录的是下一个结点在数组中的下标。
根据地址关系可以得到下面的指向：
从头结点开始，顺着next指针，就可以遍历这个链表，同时也建立起了一个单链表：
接下来的问题就是如何把这单链表逆序。
单链表的逆转
逆转后的链表形态：
如何实现呢？
new指针：新的已经逆转的链表的头结点
old指针：指向当前还没有完成逆转的老链表的头结点
tmp指针：记录老链表的头结点的后一个结点，否则后面的没有逆转的链表就被丢掉了
一开始的时候三个指针的指向：
记住了3的位置后，就可以把2的指针反向使它指向1：
完成这步之后，指针向前位移，new指向当前逆转链表的头结点，old指向当前还没有逆转的链表的头结点，tmp指向old的下一个结点：
重复上面的步骤：
以此类推，一直重复k步。
所以就需要一个计数器，需要逆序的结点达到k时，停下来，（上图就是样例中k = 4的时候），此时结点1的指向是不对的，应该指向结点5，即是当前还没有逆转的老的链表的头结点：
空的头结点应该指向4，即当前已经逆转的链表的头结点，也就是new指针所指的位置：
伪代码：如果没有K的限制，整个链表逆转，那么当old 为空的时候，逆转结束。
参数head默认指向的是空的头结点，因为有K的限制，所以：
测试数据
这篇关于MOOC 数据结构 | 2. 线性结构（6）：习题选讲---Reversing Linked List的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
