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

又到一年一次的招聘季，很多莘莘学子该忙起来了，复习基础知识，搜索面试题。面试题里面比较经典的是单向链表反转，就是一个单向链表，就地反转。这个面试题主要考查：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;

调了一下，通了。