// PartReverse.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <cstdlib>
#include <iostream>
using std::cout;
using std::endl;
typedef struct SNode {
int value;
SNode *pNext;
SNode(int v):value(v),pNext(NULL){}
}SNode;
void Print(SNode* head) {
SNode* p = head->pNext;
while (p) {
cout << p->value;
p = p->pNext;
if (p)
cout << "->";
}
cout << endl;
}
void Destroy(SNode* head) {
while (head)
{
SNode* p = head;
head = head->pNext;
delete p;
}
}
void PartReverse(SNode *head, int m, int n) {
SNode* p = head;
SNode* pNext = NULL;
int i = 1;
//找到第m个数的前驱
while (i < m) {
p = p->pNext;
i++;
}
//移动结点
i = 0;
//记录被交换的第一个结点
SNode* initNext = p->pNext;
//pNext指向被交换的第二结点
pNext = p->pNext->pNext;
while (i<n-m)
{
SNode* pCur = pNext;
pNext = pNext->pNext;
//头插法
pCur->pNext = p->pNext;
p->pNext = pCur;
i++;
}
//pNext指向被移动最后一个结点的下一结点
initNext->pNext = pNext;
}
int main()
{
SNode* head = new SNode(0);
for (int i = 0; i < 13; i++) {
SNode* p = new SNode(rand() % 10);
p->pNext = head->pNext;
head->pNext = p;
}
cout << "Before:\t";
Print(head);
PartReverse(head, 6, 9);
cout << "After:\t";
Print(head);
Destroy(head);
system("pause");
return 0;
}