首页 > 代码库 > 链表的反转

链表的反转

题目:给出一个连续的链表,要求你将其结构改变反转。

例如:

   输入:1 2 3 4 5

   输出:5 4 3 2 1


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//定义链表的结构
typedef struct ListNode{
	int m_pKey;
	ListNode * m_pNext;
};

//链表的反转
ListNode *ListReverse(ListNode *pHead)
{
    ListNode *pCurrent,*pReversedHead;
	pReversedHead = NULL;
	pCurrent = pHead->m_pNext;
	while(pCurrent != NULL)
	{
		ListNode *pTemp = pCurrent;        //取下当前的点
		pCurrent = pCurrent->m_pNext;      //移到下一个点
		pTemp->m_pNext = pReversedHead;    //将当前的点插入反转后链表的头部
		pReversedHead = pTemp;
		/*printf(" %d  ",pCurrent->m_pKey);*/
	}
	return pReversedHead;
}
int main()
{
	ListNode *Head,*Root,*p;   //Head 链表的头,Root 输入的链表
	int value;
	Root = (ListNode *)malloc(sizeof(ListNode));
	Root->m_pNext = NULL;
	Head = Root;                   
	while(scanf("%d",&value)!=EOF)
	{
		p = (ListNode *)malloc(sizeof(ListNode));
		//尾插法
		p->m_pKey = value;      //赋值
		p->m_pNext = NULL;             
		Root->m_pNext = p;     //插入到链表的尾部
		Root = p;              //链表移动到下一个点

	    /*
		    //头插法
		    p->m_pKey = value;
		    p->m_pNext = Root;
		    Root = p;
		*/
	}
    ListNode * q = ListReverse(Head);
	while(q != NULL)
	{
		printf("%d ",q->m_pKey);
		q = q->m_pNext;
	}
	printf("\n");
	return 0;
}