学步园

关于线性链表的逆序可用循环和递归的两种方式完成，逆序的递归方式比较难理解，主要是返回头结点的问题。

链表节点定义如下：

//定义线性链表结点
typedef struct node {
    int data;
    struct node *link;
}LNode, *LinkList;

循环方式完成逆序：

//逆转线性链表
LinkList reverseList(LinkList head)
{
    LinkList reversedHead = NULL;
    LinkList pPrev = NULL;
    LinkList pNode = head;

    while(pNode != NULL)
    {
        LinkList pNext = pNode->link;
        if(pNext == NULL)
            reversedHead = pNode;

        pNode->link = pPrev;
        pPrev = pNode;
        pNode = pNext;
    }

    return reversedHead;
}

递归方式完成递归：

LinkList reverseList2(LinkList head)
{
    if(head == NULL || head->link == NULL)
        return head;

    LinkList newHead = reverseList2(head->link);
    head->link->link = head;
    head->link = NULL;

    return newHead;
}

基本功能的测试代码如下：

/*
 * =====================================================================================
 *
 *       Filename:  reverseLink.c
 *
 *    Description:  逆转线性链表
 *
 *        Version:  1.0
 *        Created:  2012/10/18 15时28分00秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (), 
 *   Organization:  
 *
 * =====================================================================================
 */
#include <stdlib.h>
#include <stdio.h>

//定义线性链表结点
typedef struct node {
    int data;
    struct node *link;
}LNode, *LinkList;

//逆转线性链表
LinkList reverseList(LinkList head)
{
    LinkList reversedHead = NULL;
    LinkList pPrev = NULL;
    LinkList pNode = head;

    while(pNode != NULL)
    {
        LinkList pNext = pNode->link;
        if(pNext == NULL)
            reversedHead = pNode;

        pNode->link = pPrev;
        pPrev = pNode;
        pNode = pNext;
    }

    return reversedHead;
}  
 
LinkList reverseList2(LinkList head)
{
    if(head == NULL || head->link == NULL)
        return head;

    LinkList newHead = reverseList2(head->link);
    head->link->link = head;
    head->link = NULL;

    return newHead;
}

//打印线性链表
void printList(LinkList list)
{
    LinkList p = list;
    while( p != NULL )
    {
        printf("%d ", p->data);
        p = p->link;
    }

    printf("\n");
}

//创建线性链表
void creatList(LinkList *list)
{
    int a[] = {0, 1, 2, 3, 4, 5, 6, 7};
    LinkList previous;
    for( int i = 0 ; i < sizeof(a)/sizeof(int); ++i )
    {
        LinkList p = (LinkList)malloc(sizeof(LNode));
        if( p != NULL )
        {
            p->data = a[i];
            p->link = NULL;
        }
        if( *list == NULL )
        {
            *list = p;
            printf("*list == NULL\n");
        }
        else
            previous->link = p;

        previous = p;
    }
}

int main()
{
    LinkList list = NULL;
    creatList(&list);
    printList(list);

    LinkList reversedList = reverseList(list);
    printList(reversedList);
    LinkList reversedList2 = reverseList2(reversedList);
    printList(reversedList2);
}