反转链表（C语言）

 本题要求实现一个反转链表

1 2 3 4 5 6

6 5 4 3 2 1

#include
#include
#include
typedef struct st{
	int data;
	struct st * Next;
}NODE,*PNODE; 
PNODE creat_list();
void traverse_list1(PNODE pHead);
void traverse_list2(PNODE pHead);
PNODE reverse_list(PNODE pHead );
void traverse_list(PNODE pHead);
int main(void)
{
	PNODE pHead=NULL;
	pHead=creat_list();//创建 
	printf("链表反转前的数据n");
	traverse_list1(pHead);
	
	pHead=reverse_list(pHead->Next);//反转 
	printf("链表反转后的数据n");
	traverse_list2(pHead);
	free(pHead);
}
//创建单链表 
PNODE creat_list()
{
	int len;
	int i;
	int val;
	PNODE pHead=NULL;
	pHead=(PNODE)malloc(sizeof(NODE));
	if(NULL==pHead)
	{
		printf("分配内存失败，请重新输入"); 
	}
	PNODE pTail=pHead;
	pTail->Next=NULL;
	printf("请您输入需要链表的的个数%d",len); 
	scanf("%d",&len);
	for(i=0;idata=val;
		pTail->Next=pNew;
		pNew->Next=NULL;
		pTail=pNew;
		}
		
	}
	return pHead;
}
//遍历输出 
void traverse_list1(PNODE pHead)
{
   PNODE p=NULL;
   p=pHead->Next;
   while(p)
    {
	    printf("%d ",p->data);
    	p=p->Next;
    }	
    printf("n");
}

void traverse_list2(PNODE pHead)
{
   PNODE p=NULL;
   p=pHead;
   while(p)
    {
	    printf("%d ",p->data);
    	p=p->Next;
    }	
    printf("n");
}
//非递归反转 

//递归反转 
PNODE reverse_list(PNODE pHead){
    if(pHead==NULL||pHead->Next==NULL){
        return pHead;
    }
    PNODE cur=reverse_list(pHead->Next);
    pHead->Next->Next=pHead;
    pHead->Next=NULL;
    return cur;
}

在本题中可以采用两种方法，就地反转和非递归反转（这个有些不懂）

就地反转，将第二个节点的指针域指向第一个节点，然后循环依次往复。

注意：在这边需要注意的是，在指向过程中要断开将其第一个节点和第二个指针的连接，否则会造成循环链表。数据也会出现错误。