链表逆置

上次用堆栈实现对链表的逆置,比较麻烦。这次换了个算法,下面主要有两种实现算法。

算法一


首先想到的肯定是创建一个新的空链表,然后把旧的链表中的元素通过指针p从头到尾遍历,每遍历一个,就把该元素从链表中脱离,添加到新的链表的头部,新建空链表的时候可以初始化一个空的无用节点(仅仅是为了操作方便)。

算法二


不通过新建一个新链表,具体是让第一个节点的指针域为NULL,第二个指针域指向第一个节点,第三个指向第二个~~~~~~L指向最后一个节点。

下面是代码:

[code]
#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
int data;
struct Node *Next;
}Node, *pNode;

void InitialNode(pNode *node);//Intial Node
void ReverseLink(pNode L);//reverse Link by creating a new link
void PrintLink(pNode L);//print Link
void ReverseLink2(pNode L);//reverse Link not by creating a new link

int main()
{
Node Header; //define the first for no use
Header.data = 0;
Header.Next = NULL;
pNode pTemp = &Header;
for(int i = 0;i < 10; ++i) //initial Link,date is for debug
{
pNode pNew;
InitialNode(&pNew);
pNew->data = i;
pTemp->Next = pNew;
pTemp = pNew;
}
PrintLink(&Header);
//ReverseLink(&Header);//opentional
ReverseLink2(&Header);
return 0;
}

void InitialNode(pNode *node)
{
*node = (pNode)calloc(1,sizeof(Node));
if(!*node)
{
printf("Error");
return ;
}
(*node)->data = 0;
(*node)->Next = NULL;
}

void PrintLink(pNode L)
{
int i = 0;
pNode p = L;
while(p)
{
printf("node %d : %d\n",i,p->data);
p = p->Next;
}
printf("\n\n");
}

void ReverseLink(pNode L)
{
pNode q = NULL;
pNode p = L;
pNode pNewLink;
InitialNode(&pNewLink);
while(p)
{
q = pNewLink->Next;
pNewLink->Next = p;
p = p->Next;
pNewLink->Next->Next = q;
}
printf("reverse Link 1 : \n");
PrintLink(pNewLink);
}

void ReverseLink2(pNode L)
{
pNode p = L;
pNode r = NULL;
pNode q = p->Next;
while(q)
{
r = q->Next;
q->Next = p;
p = q;
q = r;
}
L->Next = NULL;
L = p;
printf("reverse Link 2 : \n");
PrintLink(L);
}
[/code]

标签:DataStructure