链表逆置

谁践踏了优雅 2022-06-16 11:46 221阅读 0赞

### 算法一 ###

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

### 算法二 ###

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

下面是代码：

#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);
    }