数据结构--链表反转

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

/*
---------------------
输出
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> NULL
---------------------
*/
typedef int ElemType;
typedef struct ListTag{
	ElemType data;
	struct ListTag * next;
}List, * PtList;
 
void InitList(PtList ptlist);
void show(PtList ptlist);
PtList reversed(PtList ptlist);

int main()
{
	List list, *head;
	head = &list;
	list.data = 0;
	list.next = NULL;
	InitList(head);
	show(head);
	
	show(reversed(head));
	
	return 0;
}

void InitList(PtList ptlist)
{
	PtList new_plist;
	ElemType origindata[9] = {1,2,3,4,5,6,7,8,9};
	unsigned int len = sizeof(origindata)/sizeof(ElemType);
	for(int i=0; i<len; i++)
	{
		new_plist = (PtList)malloc(sizeof(List));
		if(!new_plist)
			exit(1);
		new_plist->data = origindata[i];
		ptlist->next = new_plist;
		ptlist = new_plist;
	}
	ptlist->next = NULL;
}

void show(PtList ptlist)
{
	while(ptlist)
	{
		printf("%d -> ", ptlist->data);
		ptlist = ptlist->next;
	}
	printf("NULL");
	putchar('
');
}

PtList reversed(PtList phead)
{
	/*反转列表*/
	if(phead==NULL || phead->next==NULL)
		exit(1); 
	PtList pre = phead;//规划好各节点位置 
	PtList cur = phead->next;
	PtList next;
	pre->next = NULL;//第一步 头结点指向NULL 
	while(cur != NULL)
	{
		next = cur-> next;//第二步 保留next节点地址（因为cur要指向pre了而非之前的next） 
		cur->next = pre;//第三步 cur指向pre 
		pre = cur;//第四步 pre移动到下个节点 
		cur = next;//同样 cur移动到下个节点 
	}
	return pre;
}