Question

【数据结构·C语言】请高手帮忙检查一个关于【实现链表的就地逆置的算法】是否正确

另：因为我是自学的数据结构，所以任何方面都有可能出问题，希望能够帮忙指出，不厌其详，谢谢！！！

对单链表实现就地逆置。

status Inverse_L(LinkList &L)
{
LinkList s , p;
for (i=1; i<=L.length-1;i++)
{
for(;p->next->next!=NULL;p=p->next);
p->next->next=s->next; s->next=p->next;
p->next=NULL;
s=s->next;
p=s ;
}
return OK;
}//Inverse_L

这种算法是不是比较复杂啊？时间复杂度是多少？算法思想有哪里可以改进的吗？

Answer 1

我已经把你给的代码在下列代码中做了具体实现，具体问题已在下列代码中说明

#include <iostream>
using namespace std;
#define OK true
#define FALSE false
typedef bool status;
typedef int INT32;

typedef struct tagLinkNode
{
INT32 key;
struct tagLinkNode *next;
tagLinkNode()//construct
{
key = -1;
next = NULL;
}
}LinkNode, *LinkList;

status createLinkList( LinkList &L)
{
INT32 nAccount = 0 ;//number of node in LinkList L
cout<<"input the num of node,please"<<endl;
cin>>nAccount;
//
//the first node is empty
//
L = ( LinkList ) malloc( sizeof( LinkNode) );
L->next = NULL;
LinkList pNow = L;

//create list
cout<<"import data:"<<endl;

for( INT32 i = 0; i<nAccount; i++ )
{
LinkList pTemp = ( LinkList ) malloc( nAccount * sizeof( LinkNode ) );
if( pTemp == NULL ) return FALSE;
pTemp->next = NULL;
INT32 nKey;
cin>>nKey;
pTemp->key = nKey;
pNow->next = pTemp;
pNow = pTemp;
}
return OK;
}
void clearLinkList( LinkList &L )
{
LinkList pNow = L;

while( pNow != NULL )
{
LinkList pTemp = pNow->next;
free( pNow );
pNow = pTemp;
}

L = NULL;
return ;
}
status inverseLinkList( LinkList &L )//这里的status说明你的代码应该是仿照书来写的，书上的代码一般是伪码
{
LinkList pNow = L,pTemp = L;// 你没有赋值
while( pNow != NULL )//traverse in first loop
{
//
//下面这句是不安全的，你没有判断pTemp->next的有效性
//
/*for( ; pTemp->next->next != NULL; pTemp = pTemp->next );*/

if( pTemp->next == NULL ) break;
if( pTemp->next->next == NULL )// 避免第一个节点丢失
{
break;
}

for( ; pTemp->next->next != NULL; pTemp = pTemp->next );//traverse in second loop 很显然算法的时间复杂度为0(n^2)
//
//下面三行代码有问题的，会丢失原链表中的第一个节点
//
pTemp->next->next = pNow->next;
pNow->next = pTemp->next;
pTemp->next = NULL;

pNow = pNow->next;
pTemp = pNow;
}
return OK;
}
void displayLinkList( LinkList L )
{
LinkList pNow = L->next;
cout<<"print LinkList:"<<endl;

while( pNow != NULL )
{
cout<< pNow->key <<" ";
pNow = pNow->next;
}
cout<<endl;
return ;
}
int main()
{
LinkList L = NULL;
createLinkList( L );// create LinkList

cout<<"before the operation of inversing"<<endl;
displayLinkList( L );

inverseLinkList( L );

cout<<"after the operation of inversing"<<endl;
displayLinkList( L );

clearLinkList( L );

system("pause");
return 0;
}