PAT 解题报告 1074. Reversing Linked List (25)

1074. Reversing Linked List 题目描述:

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.

反转链表, 每隔K个反转一次, 例子见上面.

1074. Reversing Linked List 算法分析:

其实就是个模拟题, 改怎么反转就怎么反转, 就是测试用例比较恶心, 注意输入可能不止一个链表的情况, 这种情况下, 要忽略那些不在该链表(输入中的head对应的那个链表)上的节点, 也就是有效节点数(输出的节点个数)比输入中的N要小. 题目的输入使用了数组形式的链表, 可以事先就开好一个足够大的数组, 反转的过程就是一般的反转了, 注意记录下反转以后新的链表头尾, 还有不要忘记把每段反转以后的新的链表接起来. AC代码如下:

#include <cstdio>

struct Node {
	int iData;
	int iNext;
};

const int iMaxLen = 100004;

int iHead;
int N, K;
Node NodeList[iMaxLen];

void doPrint(int iListHead) {
	while(-1 != iListHead) {
		if(NodeList[iListHead].iNext == -1) {
			printf("%.5d %d -1\n",
				iListHead,
				NodeList[iListHead].iData);
			break;
		}
		printf("%.5d %d %.5d\n",
			iListHead,
			NodeList[iListHead].iData,
			NodeList[iListHead].iNext);
		iListHead = NodeList[iListHead].iNext;
	}
}

int reverseK(int iStartHead, int iK,
			 int *pHead, int *pTail) {
	if(-1 == iStartHead || iK <= 1)
		return -1;
	if(2 == iK) {
		int node1 = iStartHead;
		int node2 = NodeList[iStartHead].iNext;
		NodeList[node1].iNext = NodeList[node2].iNext;
		NodeList[node2].iNext = node1;

		*pHead = node2;
		*pTail = node1;
		return 0;
	}
	*pTail = iStartHead;
	int node1 = iStartHead;
	int node2 = NodeList[iStartHead].iNext;
	int nodeTmp = -1;
	for(int i = 0; i < iK - 1; ++i) {
		nodeTmp = NodeList[node2].iNext;
		NodeList[node2].iNext = node1;
		node1 = node2;
		node2 = nodeTmp;
	}
	*pHead = node1;
	NodeList[*pTail].iNext = node2;
	return 0;
}

void gao() {
	int iNodeTmp = iHead;
	int iEffectiveLength = 1;
	while(-1 != NodeList[iNodeTmp].iNext) {
		++iEffectiveLength;
		iNodeTmp = NodeList[iNodeTmp].iNext;
	}

	if(K > iEffectiveLength) {
		doPrint(iHead);

	}
	N = iEffectiveLength;

	int iNewHead;
	if(K > 1) {
		int iTheHead, iTheTail;
		int iLastTail;
		// first init reverse to decide the new head
		reverseK(iHead, K, &iTheHead, &iTheTail);
		iNewHead = iTheHead;
		iLastTail = iTheTail;
		int iReverseCount = N / K - 1;
		for(int i = 0; i < iReverseCount; ++i) {
			reverseK(NodeList[iTheTail].iNext, K, &iTheHead, &iTheTail);
			NodeList[iLastTail].iNext = iTheHead;
			iLastTail = iTheTail;
		}
	}
	else
		iNewHead = iHead;
	doPrint(iNewHead);
}

int main() {
	for(int i = 0; i < iMaxLen; ++i) {
		NodeList[i].iData = 0;
		NodeList[i].iNext = -1;
	}
	scanf("%d %d %d", &iHead, &N, &K);
	int iSingleNodeAddress, iSingleNodeData, iSingleNodeNext;
	for(int i = 0; i < N; ++i) {
		scanf("%d %d %d", &iSingleNodeAddress, &iSingleNodeData, &iSingleNodeNext);
		NodeList[iSingleNodeAddress].iData = iSingleNodeData;
		NodeList[iSingleNodeAddress].iNext = iSingleNodeNext;
	}
	gao();
	return 0;
}

1074. Reversing Linked List 注意点:

(1) 这次PAT最坑的一个题目吧, 输入可能不止一个链表, 有些节点不在要反转的那个链表上, 输出的时候应当忽略. 比如

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 -1
99999 5 68237
12309 2 33218

(2) 另外注意指针的使用, 还有特例K = 1, K = N之类的情况, 因为上面的特殊坑点, 有可能是打断了的多个链表, 我们的K也有可能大于有效节点数.

Written on March 6, 2014