程序员面试宝典之单链表反转

欢迎大家来到IT世界,在知识的湖畔探索吧!

题目：给定一个单链表的头指针，如何将所有节点的指针反转（要求就地反转）,并且返回新的头节点，如图：

欢迎大家来到IT世界,在知识的湖畔探索吧!

Node* ReverseList(Node* pHead) Node*{

}

难度：四星

面试频率：三星

这道题在10年前是一道高频题，据说最早由微软发明专门用来面试，可见这道题多么适合面试，但是由于这道题太有名以至于近年来面试频率有所下降，而且这道题不太方便直接运行，所以不太容易出现在机试和在线可运行环境的面试中。它比较容易出现在笔试中。

思路：

由于题目要求就地反转，而且参数只有头指针。那么重新构造链表的思路不可取，此时自然想到了双指针法

首先定义结构：

struct Node {

int data;

Node *next

}

此时要把一个指针指向前面的节点。那么前面的节点必然要在循环中定义出来

Node *pPre;

在循环中，首先必然要将next指针转向，因此必然有语句

pPre = pNode->next;

原next指针要断开

pPre->next = NULL;

反转后。必然要将pPre和pNode向后推进，而且原next指针已经断开，因此必然有语句

pPrev = pNode;

pNode也需要向后推进

pNode = pNode->next

那么循环体的判断结束条件就是pNode != NULL或者pNode->next != NULL,但由于头节点pHead后面的第一个节点可能就是空，也就是说链表可能只有一个头节点。因此还是用pNode来判断

while( pNode != NULL)

由于题目只给到了参数pHead,那么最初始的pNode 就是pHead的next

pNode = pHead->next;

C语言源代码如下：

Node* ReverseList(Node* pHead) Node*{

Node *pNode = pHead->next;

Node *pPre = pHead;

while( pNode != NULL){

pPre = pNode->next;

pNode->next = NULL;

pPrev = pNode;

pNode = pNode->next;

}

return pPre;

}

最终pNode将被赋值NULL。循环体结束，pPre成了最后一个节点。也就是反转后的新头节点

测试整个链表只有一个头节点的情况，pNode直接为NULL。略过循环体。pPre还是等于参数pHead,返回pPre无误