題目:
原連結清單為1->2->3->4->5->6->7
k=3的子段逆轉結果為
3->2->1->6->5->4->7
code:
關鍵點
首子段要記錄整個連結清單的頭指針,記錄相鄰兩字段的尾節點
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <hash_map>
using namespace std;
typedef struct node
{
int data;
struct node* next;
}*pList,Node;
void rReverse(pList &list,int k)
{
pList p=list, tail, pretail;
tail=p;
int flag=0;
while(p!=NULL)
{
int n=k;
pList post=p->next;
tail=p;
while(post!=NULL && n--!=1)
{
pList temp=post->next;
post->next=p;
p=post;
post=temp;
}
if(post!=NULL && flag==0)
{
list=p;
pretail=tail;
flag=1;
p=post;
}
else if(post!=NULL)
{
pretail->next=p;
pretail=tail;
p=post;
}
else
{
pretail->next=p;
tail->next=NULL;
break;
}
}
}
int s[7]={1,2,3,4,5,6,7};
void createList(pList& head)
{
head=new Node;
pList p=head;
for(int i=0;i<7;i++)
{
p->next=new Node;
p->next->data=s[i];
p=p->next;
}
p->next=NULL;
p=head;
head=head->next;
delete p;
}
void showList(pList head)
{
pList p=head;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int main(void)
{
pList head;
createList(head);
showList(head);
rReverse(head,4);
showList(head);
system("pause");
return 0;
}