图解带头节点的单链表的反转操作
前言
对单链表进行反转是一个很基本的算法。下面将介绍3种不同的单链表反转操作，需要注意的是，我们所讨论的单链表是包含头节点的。
我们的链表节点和main函数以及部分函数的代码如下：
1 #include2 3 struct LNode { 4 int data; 5 LNode *next; 6 }; 7 8 LNode* read(); 9 void print(LNode *L); 10 11 int main() { 12 LNode *L1, *L2; 13 L1 = read(); 14 L2 = reverse3(L1); 15 print(L2); 16 17 return 0; 18 } 19 20 LNode* read() { 21 LNode *head = new LNode; // 申请一个链表节点做为头节点 22 head -> next = NULL; 23 LNode *last = head; // last指针用于指向最后一个节点，我们通过尾插法进行插入 24 25 int n; 26 scanf("%d", &n); 27 while (n--) { 28 LNode *p = new LNode; 29 scanf("%d", &p -> data); 30 p -> next = NULL; 31 last = last -> next = p; 32 } 33 34 return head; 35 } 36 37 void print(LNode *L) { 38 L = L -> next; // 因为链表带有头节点，我们需要在头节点的下一个节点才开始遍历输出 39 while (L) { 40 printf("%d ", L -> data); 41 L = L -> next; 42 } 43 putchar('\n'); 44 }
1、迭代反转链表
1 LNode* reverse(LNode *L) { 2 LNode *preNode = NULL, *curNode = L -> next; 3 while (curNode) { 4 LNode *nextNode = curNode -> next; 5 curNode -> next = preNode; 6 preNode = curNode; 7 curNode = nextNode; 8 } 9 L -> next = preNode; 10 11 return L; 12 }
需要说明的是curNode指向的是当前需要反转的节点。
preNode指向的是当前节点的上一个节点，也就是curNode所指向的节点的上一个节点。
而nextNode指向的是下一个节点，也就是curNode所指向的节点的下一个节点，因为当前节点指向上一个后，该节点原本存有的后续节点的地址就丢失了，所以我们需要nextNode来存放后续节点的地址。
现在我们先创建一个存放着4个数据的链表。然后，第一次进入循环，执行完上述第4行代码后，有如下图：
重复上面的步骤，在第二次的循环结束后，变化为下图：
继续重复，当我们走完了循环后，整个链表就会变为下面这个样子：
我们发现头节点并没有指向存放着数据4的这个节点，所以退出了循环后，就要让头节点指向存放着数据4的这个节点，而此时preNode正指向它，所以我们可以直接执行L -> next = preNode; 也就是执行第9行这个语句。之后，链表就完成了反转，变成下面这个样子，然后返回头指针L，就通过迭代这个方法完成了整一个链表反转的操作。
2、就地逆置法反转链表
1 LNode* reverse(LNode *L) { 2 LNode *curNode = L -> next; 3 L -> next = NULL; 4 while (curNode) { 5 LNode *nextNode = curNode -> next; 6 curNode -> next = L -> next; 7 L -> next = curNode; 8 curNode = nextNode; 9 } 10 11 return L; 12 }
curNode指向的是当前需要反转的节点。
同样的，我们需要一个nextNode来存放后续节点的地址。
与上述的迭代反转不同，我们是把当前的节点插入到头节点之后，也就是通过头插法把每一个节点插到头节点之后。
一样，现在我们先创建一个存放着4个数据的链表。在进入循环之前，我们先要让头节点指向NULL，不过在此之前，需要用curNode来保存头节点所指向的节点的地址，也就是第1个存放数据的节点的地址。
然后，第一次进入循环，执行完上述第4行代码，有如下图：
重复上面的步骤，在第二次的循环结束后，变化为下图：
继续重复，当我们走完了循环后，整个链表就会变为下面这个样子：
循环结束后，我们的链表反转操作也结束了，接下来只需要返回头指针L就可以了。
3、递归反转链表
1 LNode* reverseFrom2Node(LNode *L) { 2 L -> next = reverse(L -> next); 3 return L; 4 } 5 6 LNode* reverse(LNode *L) { 7 if (L == NULL || L -> next == NULL) { 8 return L; 9 } 10 LNode *last = reverse(L -> next); 11 L -> next -> next = L; 12 L -> next = NULL; 13 14 return last; 15 }
看不懂？先不要急！
先补充说明，在上述代码中，reverse函数可以对不带头节点的链表进行反转操作，也就是说，如果链表不带有头节点，只需要通过reverse函数就可以完成整一个链表的反转。但是，由于我们的链表带有头节点，如果只调用reverse函数就行不通了。所以我们还需要另一个函数reverseFrom2Node（正如函数名一样，从第二个节点开始反转）。
为了方便说明，我们先假设链表不带有头节点，先来看看reverse函数是如何工作的。
对于这个递归算法，我们首先要明确这个递归的定义。
就是，我们传入一个头指针L，然后将以头指针为起点的链表进行反转，并返回反转后的链表的第一个节点的地址。而当链表的长度为1，也就是只有一个节点时，由于反转后还是其自身，所以返回的依然是原来传入的那个头指针。注意，此时我们的链表不带有头节点。接下来，我们对下面这个链表执行reverse函数，进行递归反转。
第一次进入reverse函数后，由于L -> next != NULL，所以不会进入到选择语句中。然后我们执行第10行，进行第一次递归。
不要跳进递归里面去！而是要根据刚才的递归函数定义，来弄清楚这行代码会产生什么结果：
第10行代码执行完后，整个链表就会变成这样子，根据定义，reverse返回的是反转后链表的第一个节点的地址，我们用last来接收，如图：
接下来是第11行的代码，目的是让上图的第二个节点（从左到右数）指向第一个节点（从左到右数），执行完后如下：
第12行代码就是让L指向的那个节点，也就是第一个节点指向NULL。
之后我们return last，就将整一个链表进行反转，并返回反转后的链表的头节点。
OK，现在你应该理解了reverse函数是如何工作的了。接下来解释reverseFrom2Node这个函数。
在解释reverse函数中，我们的链表是不带有头节点的。现在，我们的链表又带有头节点了。
你可能会问，如果我们让带头节点的链表直接执行reverse这个函数，会产生什么样的结果。正如我们前面所说的，reverse函数是将链表的第一个节点到最后一个节点进行反转，并没有说可以只反转其中一个部分。如果让带头节点的链表执行reverse函数，就会变成下面这样子：
很明显，这不是我们想要的结果。
我们其实是想让头节点之后的剩下节点进行反转，然后再将头节点指向last所指向的这个节点，也就是这样子：
为了达到这个目的，其实我们只要给reverse函数传入L -> next，不就可以了吗。也就是说，我们只反转除头节点之外的剩下部分的节点，而不反转头节点。reverse调用结束后（注意，并不是执行完第2行的代码后），会返回反转后链表的第一个节点的地址，（也就是上图对应的last所指向的节点，只是在我们的代码种并没有last这个中间变量，而是将reverse返回的值直接赋值给L -> next），如图：
此时，我们只需要L -> next = last，就可以完成整一个链表的反转了。
在上面的代买中我们直接让L -> next来接收reverse返回的值，达到同样的效果。
所以，我们才定义了reverseFrom2Node这个函数。
综上，我们的递归反转是分两部进行的。由于我们的链表带有头节点，所以需要先让除头节点之外剩余节点进行反转，也就是执行reverse(L -> next); 然后再让头节点来接收reverse函数返回的反转后的链表的第一个节点的地址，从而完成了整一个链表的反转。
到这里，我们已经解释完递归反转是如何实现的了。
其实，还有一种算法是只对链表中的第n个到第m个节点进行反转，上述只是该算法的一种特殊情况，也就是让链表中第2个节点到最后一个节点进行反转。如果要实现链表中的第n个到第m个节点反转，相关的代码就完全不是我们上面的那个样子了。
关于这个算法，可以参考：如何递归反转链表 —— https://zhuanlan.zhihu.com/p/86745433
结语
就此，关于带有头节点的单链表反转操作的3种方法已经介绍完了，下面再附上包含这3种反转方法的完整代码：
1 #include2 3 struct LNode { 4 int data; 5 LNode *next; 6 }; 7 8 LNode* read(); 9 void print(LNode *L); 10 LNode* reverse1(LNode *L); 11 LNode* reverse2(LNode *L); 12 LNode* reverseFrom2Node(LNode *L); 13 LNode* reverse3(LNode *L); 14 15 int main() { 16 LNode *L1, *L2; 17 L1 = read(); 18 19 // 反转的3种方法 20 // L2 = reverse1(L1); 21 // L2 = reverse2(L1); 22 // L2 = reverseFrom2Node(L1); 23 24 print(L2); 25 26 return 0; 27 } 28 29 LNode* read() { 30 LNode *head = new LNode; 31 head -> next = NULL; 32 LNode *last = head; 33 34 int n; 35 scanf("%d", &n); 36 while (n--) { 37 LNode *p = new LNode; 38 scanf("%d", &p -> data); 39 p -> next = NULL; 40 last = last -> next = p; 41 } 42 43 return head; 44 } 45 46 void print(LNode *L) { 47 L = L -> next; 48 while (L) { 49 printf("%d ", L -> data); 50 L = L -> next; 51 } 52 putchar('\n'); 53 } 54 55 // 迭代反转链表 56 LNode* reverse1(LNode *L) { 57 LNode *preNode = NULL, *curNode = L -> next; 58 while (curNode) { 59 LNode *nextNode = curNode -> next; 60 curNode -> next = preNode; 61 preNode = curNode; 62 curNode = nextNode; 63 } 64 L -> next = preNode; 65 66 return L; 67 } 68 69 // 就地逆置法反转链表 70 LNode* reverse2(LNode *L) { 71 LNode *curNode = L -> next; 72 L -> next = NULL; 73 while (curNode) { 74 LNode *nextNode = curNode -> next; 75 curNode -> next = L -> next; 76 L -> next = curNode; 77 curNode = nextNode; 78 } 79 80 return L; 81 } 82 83 // 递归反转链表 84 LNode* reverseFrom2Node(LNode *L) { 85 L -> next = reverse3(L -> next); 86 return L; 87 } 88 89 LNode* reverse3(LNode *L) { 90 if (L == NULL || L -> next == NULL) { 91 return L; 92 } 93 LNode *last = reverse3(L -> next); 94 L -> next -> next = L; 95 L -> next = NULL; 96 97 return last; 98 }
感谢你的阅读！
参考资料
如何递归反转链表：https://zhuanlan.zhihu.com/p/86745433