【剑指Offer面试题】 九度OJ1518：反转链表

与其非常快写出一段漏洞百出的代码，倒不如细致分析再写出鲁棒的代码。

提前想好測试用例（输入非空等等）进行測试改动代码。

题目链接地址：

http://ac.jobdu.com/problem.php?pid=1518

题目1518：反转链表

时间限制：1 秒内存限制：128 兆特殊判题：否提交：2606解决：957

题目描写叙述：

输入一个链表，反转链表后。输出链表的全部元素。

(hint : 请务必使用链表)

输入：

输入可能包括多个測试例子，输入以EOF结束。

对于每一个測试案例。输入的第一行为一个整数n(0<=n<=1000)：代表将要输入的链表的个数。

输入的第二行包括n个整数t(0<=t<=1000000)：代表链表元素。

输出：

相应每一个測试案例，

以此输出链表反转后的元素，如没有元素则输出NULL。

例子输入：

5

1 2 3 4 5

0

例子输出：

5 4 3 2 1

NULL

---

思路分析：

反转链表是经典的链表题。反转单链表须要将链表中的每一个结点的next指针指向该结点所相应的前一个结点。

这就会出现两个问题：

(1) 由于单链表中的结点仅仅有一个指向下一个结点的next指针，没有指向前一个结点的指针，所以须要用一个指针pPre “记录”该结点的前一个结点；

(2)当我们把链表结点的next指针改为指向该结点的前一个结点后。该结点与下一个结点的链接就断开了，所以还须要用一个指针pNext“记住”下一个结点的位置。

所以须要设置三个指针，分别指向当前要反转的节点、当前要反转节点的前一个节点、当前要反转节点的下一个节点。

须要注意的是对于空链表和长度为1的链表，直接返回。不须要进行反转操作。

时间复杂度O(n)

空间复杂度O(1)

---

代码：

/*********************************
【剑指Offer面试题】 九度OJ1518：反转链表
Author:牧之丶  Date：2015年
Email:[e-mail]
**********************************/
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include <math.h>
#include<stack>
#include <vector>
#include <iostream>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *pNext;
}LNode;

/*
反转链表。返回翻转后的头结点
*/
LNode* ReverseList(LNode* pHead)
{
    if(pHead == NULL)
        return NULL;
    if(pHead->pNext == NULL)
        return pHead;
    LNode* pCur = pHead;    //当前节点指针
    LNode* pPre = NULL;     //当前节点的前一个节点指针
    while(pCur != NULL)
    {
        LNode* pNext = pCur->pNext;//当前节点的后一个节点指针
        pCur->pNext = pPre;          //反转当前节点的指针指向前一个节点
        pPre = pCur;                //指针右移
        pCur = pNext;               //指针右移
    }
    return pPre;            //也即反转后的头指针
}

int main()
{
    int n,k;
    while(scanf("%d",&n) != EOF)
    {
        LNode* pHead=NULL;
        if (n>0)
        {
            int i,data;
            scanf("%d",&data);
            pHead =(LNode*)malloc(sizeof(LNode));   //不带头结点建单链表
            if(pHead == NULL)
                exit(EXIT_FAILURE);
            pHead->data = data;
            pHead->pNext = NULL;

            LNode* pCur = pHead;
            for(i=0;i<n-1;i++)
            {
                scanf("%d",&data);
                LNode*  pNew =(LNode* )malloc(sizeof(LNode));
                if(pNew == NULL)
                    exit(EXIT_FAILURE);
                pNew->data = data;
                pNew->pNext = NULL;
                pCur->pNext = pNew;
                pCur = pCur->pNext;
            }
        }

        LNode* pNewHead = ReverseList(pHead);
        if(pNewHead == NULL)
            printf("NULL\n");
        else
        {
            LNode* pCur = pNewHead;
            while(pCur != NULL)
            {
                //这里主要时要注意输出的格式
                if(pCur->pNext == NULL)
                    printf("%d\n",pCur->data);
                else
                    printf("%d ",pCur->data);
                pCur = pCur->pNext;
            }
        }
    }
    return 0;
}

/**************************************************************
    Problem: 1518
    Language: C++
    Result: Accepted
    Time:160 ms
    Memory:2972 kb
****************************************************************/

总结：

• 反转链表设置三个指针。分别指向当前要反转的节点、当前要反转节点的前一个节点、当前要反转节点的下一个节点。
• 功能測试提前想好測试用例。