MOOC 02-线性结构3 Reversing Linked List

MOOC 陈姥姥的数据结构作业题

Given a constant KK and a singly linked list LL, you are supposed to reverse the links of every KK elements on LL. For example, given LL being 1→2→3→4→5→6, if K=3K = 3, then you must output 3→2→1→6→5→4; if K=4K = 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 NN (≤105≤10^5​​) which is the total number of nodes, and a positive KK (≤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.

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

思路：

1.用结构数组模拟链表

2.核心的逆序怎么做

我在听完陈姥姥详细的解题思路后还是困惑了一段时间，用数组下标代替指针后，具体的 *** 作细节和边界要怎么处理；

最后我觉得给数组+1个单元作为链表的空表头，用来模拟指针链表的空表头，后面按照指针的 *** 作具体到下标 *** 作上，思路和步骤都会很清晰

即数组为100001个 而不是100000个

具体看代码（c语言）：

#include 
#define index int
#define MaxSize 100001
#define head 100000

typedef struct _Node{
	int Data;
	index Next;
}Node;

void Reverse( Node* Array,int K,int count );

int main()
{
	Node Array[MaxSize];     //连续的结构数组，其中的一部分组成链表 
	scanf("%d",&Array[head].Next);  //Array[100000]作为链表的空表头，它的.Next是链表第一个元素的数组下标
	
	int i,N,K,idx;
	scanf("%d %d",&N,&K);
	
	for(i=0;iNext 即第三个
			Temp = Array[Old].Next;
			Array[Old].Next = New;
			New = Old;
			Old = Temp;	//每次逆序后New Old 后移1位 继续逆序 
			cnt++;
		}
		
		Temp = Array[rear].Next;           //逆序完成后的收尾工作
		Array[Array[rear].Next].Next = Old;//逆序的这一段的第一个依然还是指向第二个  需要指向后面还没有逆序的第一个
		Array[rear].Next = New;            //需要把前面尾巴指向新逆序后第一个
		rear = Temp;                       //新的 逆序后的尾巴 用来接上下次逆序后的第一个元素
	}
	
}

比第一次写的清晰很多，简洁不少，提交全红的时候还是很开心的，数据结构这门课真的很锻炼思维，前路漫漫，诸君共勉。