【我要去面试】单向链表反转

又到一年一次的招聘季，很多莘莘学子该忙起来了，复习基础知识，搜索面试题。面试题里面比较经典的是单向链表反转，就是一个单向链表，就地反转。这个面试题主要考查：1. 基础知识（单向链表设计）；2. 边界条件检查（空链表、是否遍历到链表尾、链表头的处理等）；3. 代码风格等。这两天手痒，自己写了一个，调通。

这个题稍稍费心思的地方是：到底需要多少个指针来存放当前节点以及后面的节点；以及，按照什么样的一个顺序来调整节点的后继指针。

多少个临时指针呢？至少是两个，因为要反转，则必须存储当前节点以及后续节点，才能让后续节点“反转”指向当前节点；除此之外，还需存储后续节点的后续节点的位置。这样，就是三个指针。就地反转的核心是，将后继结点指向当前节点，然后将指向当前节点和后继结点的临时指针沿着链表向后移动一位；因为后继结点的next指针已经改变，则需要从第三个临时指针中获取后继的后继结点的位置，赋值给指向后继结点的临时指针。核心代码如下：

ListNode* pCur = pList; // 第一个临时指针，指向当前节点
ListNode* pNext = pList->pNext; // 第二个临时指针，指向后继结点
ListNode* pNextNext = pNext->pNext; // 第三个临时指针，指向后继的后继节点

while (pNextNext != NULL) // 遍历链表
{
pNext->pNext = pCur; // 将后继结点的next指针反转，指向当前节点
pCur = pNext; // 将第一个临时指针位置后移，指向后继结点
pNext = pNextNext; // 将第二个临时指针 位置后移，指向后继的后继节点
pNextNext = pNext->pNext; // 在上一句，pNext值已经改变，继续后移
}

// 当pNextNext指向链表尾部之后，还有两个节点的next指针没有处理：
// 1. 链表头节点；2.链表尾节点
pNext->pNext = pCur; // 反转链表尾节点的next指针（它当时运行时值是null）
pList->pNext = NULL; // 处理头结点，使之变成尾节点
pList = pNext; // 重新设定链表头的位置

有了核心代码，按照我的习惯，还是要实地测试一下，把它调通。以下是测试代码：从文件中读取一系列数字，存储在单向链表中，然后反转，并输出。

bool GetListAndRevert(const char *sFileIn, const char *sFileOut)
{
// 打开文件
ifstream in (sFileIn);
ofstream out (sFileOut);
if (!in || !out)
{
cerr << "Can not open the file" << endl;
return false;
}

// 声明链表节点
class ListNode
{
public:
int iData;
ListNode *pNext;

public:
ListNode (void) {iData=0; pNext=NULL;};
~ListNode (void) {};
};

// 定义链表
ListNode* pList = NULL;

// 从文本文件中读取数据，在此基础上生成单向链表
// 1. get the first data （单独处理链表头）
pList = new ListNode;
if (!(in >> pList->iData))
return false;
// 2. get the rest ones （pPre记录了前一个节点——刚刚读取出的节点——的位置）
int iNum = 0;
ListNode* pPre = pList;
while (in >> iNum)
{
pPre->pNext = new ListNode;
pPre->pNext->iData = iNum;
pPre = pPre->pNext;
}


// 链表反转

// 1. judge the case of empty list, and the case of single node
if (NULL == pList || NULL == pList->pNext)
return true;

// 2. judge the case of double nodes
if (NULL == pList->pNext->pNext)
{
// exchange the double nodes to each other
ListNode* p = pList;
p->pNext->pNext = pList;
pList->pNext = NULL;
pList = p;
return true;
}

// 3. the case of more than 3 nodes
ListNode* pCur = pList; // 第一个临时指针，指向当前节点
ListNode* pNext = pList->pNext; // 第二个临时指针，指向后继结点
ListNode* pNextNext = pNext->pNext; // 第三个临时指针，指向后继的后继节点

while (pNextNext != NULL) // 遍历链表
{
pNext->pNext = pCur; // 将后继结点的next指针反转，指向当前节点
pCur = pNext; // 将第一个临时指针位置后移，指向后继结点
pNext = pNextNext; // 将第二个临时指针 位置后移，指向后继的后继节点
pNextNext = pNext->pNext; // 在上一句，pNext值已经改变，继续后移
}

// 当pNextNext指向链表尾部之后，还有两个节点的next指针没有处理：
// 1. 链表头节点；2.链表尾节点
pNext->pNext = pCur; // 反转链表尾节点的next指针（它当时运行时值是null）
pList->pNext = NULL; // 处理头结点，使之变成尾节点
pList = pNext; // 重新设定链表头的位置

// 遍历链表，将结果存储到文本文件中
pCur = pList;
while (pCur != NULL)
{
out << pCur->iData << "\n";
pCur = pCur->pNext;
}

// 链表删除，内存释放
pCur = pList;
while (pCur != NULL)
{
pNext = pCur->pNext;
delete pCur;
pCur = pNext;
}
return true;

调了一下，通了。