数据结构--链表反转

#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('\n');
}

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