反转链表详解编程语言

题目：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。链表节点定义如下：

typedef int DataType; 
 
typedef struct Node 
{ 
    DataType data; 
    struct Node *next; 
}Node, *pList, *pNode;

【解题思路】
定义四个指针，一个指针用于指向链表的头节点，其他三个指针用于指向当前节点、前一个节点和后一个节点。编写代码的时候要注意链表的三种情况：空节点、两个节点和多个节点。

【代码】

Node *ReversedList(pList list) 
{ 
    assert(list); 
    pNode reseredhead = NULL; 
    pNode pre = NULL; 
    pNode cur = list; 
    pNode pnext = NULL; 
    while (cur != NULL)//注意空链表情况 
    { 
        pnext = cur->next; 
        if (pnext == NULL)//注意单节点情况 
        { 
            reseredhead = cur; 
        } 
        else 
        { 
            cur->next = pre; 
        } 
        pre = cur; 
        cur = pnext; 
    } 
    return reseredhead; 
}

【程序】

#define _CRT_SECURE_NO_WARNINGS 1 
# include <stdio.h> 
# include <stdlib.h> 
# include <assert.h> 
 
typedef int DataType; 
 
typedef struct Node 
{ 
    DataType data; 
    struct Node *next; 
}Node, *pList, *pNode; 
 
void InitLinkList(pList *pplist) 
{ 
    assert(pplist); 
    *pplist = NULL; 
} 
 
void PushBack(pList *pplist, DataType x) 
{ 
    pNode cur = *pplist; 
    pNode pnode = NULL; 
    assert(pplist); 
    pnode = (pNode)malloc(sizeof(Node)); 
    if (pnode == NULL) 
    { 
        perror("PushBack::malloc"); 
        exit(EXIT_FAILURE); 
    } 
    pnode->data = x; 
    pnode->next = NULL; 
    if (cur == NULL) 
    { 
        *pplist = pnode; 
    } 
    else 
    { 
        while (cur->next != NULL) 
        { 
            cur = cur->next; 
        } 
        cur->next = pnode; 
    } 
} 
 
void Display(pList plist) 
{ 
    pNode cur = plist; 
    while (cur) 
    { 
        printf("%d-->", cur->data); 
        cur = cur->next; 
    } 
    printf("over/n"); 
} 
 
void PrintNode(pList plist) 
{ 
    pNode cur = plist; 
    printf("%d/n", cur->data); 
} 
 
void Destroy(pList *pplist) 
{ 
    pNode cur = *pplist; 
    assert(pplist); 
    while (cur) 
    { 
        pNode del = cur; 
        cur = cur->next; 
        free(del); 
    } 
    *pplist = NULL; 
} 
 
Node *ReversedList(pList list) 
{ 
    assert(list); 
    pNode reseredhead = NULL; 
    pNode pre = NULL; 
    pNode cur = list; 
    pNode pnext = NULL; 
    while (cur != NULL) 
    { 
        pnext = cur->next; 
        if (pnext == NULL) 
        { 
            reseredhead = cur; 
        } 
        else 
        { 
            cur->next = pre; 
        } 
        pre = cur; 
        cur = pnext; 
    } 
    return reseredhead; 
} 
 
 
void test1() 
{ 
    pList plist; 
    pNode ret = NULL; 
    InitLinkList(&plist); 
    PushBack(&plist, 1); 
    PushBack(&plist, 2); 
    PushBack(&plist, 3); 
    PushBack(&plist, 4); 
    PushBack(&plist, 5); 
    PushBack(&plist, 6); 
    Display(plist); 
    PrintNode(plist); 
    ret = ReversedList(plist); 
    PrintNode(ret); 
    Destroy(&plist); 
} 
 
int main() 
{ 
    test1(); 
    system("pause"); 
    return 0; 
}

运行结果：

【测试】
1、输入的链表头指针是NULL。
2、输入的链表只有一个节点。
3、输入的链表有多个节点。

【本题扩展】
用递归实现同样的反转链表功能。

【存在的问题】
没有处理好输入的链表头指针是NULL的情况。