与其非常快写出一段漏洞百出的代码，倒不如细致分析再写出鲁棒的代码。
提前想好測试用例（输入非空等等）进行測试改动代码。
题目链接地址：
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:bzhou84@163.com
**********************************/
#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
****************************************************************/总结：
- 反转链表设置三个指针。分别指向当前要反转的节点、当前要反转节点的前一个节点、当前要反转节点的下一个节点。
- 功能測试提前想好測试用例。