get 到O(1)反转链表（尾插法）的那个点
文章目录
其实一直没完全搞明白这个尾插法。也曾自己写过好多次的原地反转链表，无不以失败告终，最后不得不在O(N)的复杂度下草草收场。 背题吧，咱也不是那块料、
今晚突然就 get 到那个点了，原来，奥妙在这里···
放码过来
极简主义，类就随意吧。
#include<iostream>
using namespace std;
class Node {
public:
Node* next; //直接放公有域里吧，省的麻烦
int val;
Node(int v) { val = v; }
Node(){}
};
Node* func(Node* head) {
Node* nowHead = head, * sourceLink = head->next, * tempNode = NULL;
while (sourceLink != NULL)
{
tempNode = sourceLink; // 把源链表首节点取出
sourceLink = sourceLink->next; // 源链表首节点后移
tempNode->next = nowHead; // 取出的节点接在目标链表的首部
nowHead = tempNode; // 目标链表首部更改为新的节点
}
head->next = NULL; // 别忘了把原先的链表头指向NULL
return nowHead;
}
int main() {
Node* node1 = new Node(1);
Node* node2 = new Node(2);
Node* node3 = new Node(3);
Node* node4 = new Node(4);
node1->next = node2;
node2->next = node3;
node3->next = node4;
Node* node = func(node1);
while (node) {
cout << node->val << endl;
node = node->next;
}
return 0;
}成环
自己写的每次都会打结，成环了。
Node* func(Node* head) {
Node* nowHead = head, * sourceLink = head->next, * tempNode = NULL;
while (sourceLink != NULL)
{
tempNode = sourceLink; // 把源链表首节点取出
sourceLink = sourceLink->next; // 源链表首节点后移
tempNode->next = nowHead; // 取出的节点接在目标链表的首部
nowHead = tempNode; // 目标链表首部更改为新的节点
}
head->next = NULL; // 别忘了把原先的链表头指向NULL
return nowHead;
}这个就不会成环吗？一眼我就看出来会成环。 只要有这一行在，就绝对是要成环的：
tempNode->next = nowHead;为什么？经验，自己想想。
破解
其实知道它会成环，在看两眼，也就看到玄机了。
成环有几个问题存在？ 1、死循环，稍微学过链表都应该要知道这个吧。 2、无法联系到后面的节点。
先不管第一点，能想到第二点，就明白了。 我在你成环之前把后面被环屏蔽的节点事先取出来，在你成环之后重新给你接上去，破坏你的闭环。
关键就在这一行的位置：
sourceLink = sourceLink->next;晚写一步，就玩不转了。
调试验证
那么，现在用眼睛看出来的有： 1、取出环后节点； 2、反转成环； 3、破坏闭环； 4、返回第一步，直到退出条件成立。
初始状态：
在这里插入图片描述
取出后面的节点：
在这里插入图片描述
在这里插入图片描述
依旧是要成环的：
在这里插入图片描述
看到没，依旧是要成环的。
那最后呢？
在这里插入图片描述
最后一个节点是谁？是head。 所以最后的善后操作谁来，head来，把环收了：
head->next = NULL;全程就是这么的一气呵成，再也不用去死记硬背了。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/09/23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
