其实一直没完全搞明白这个尾插法。也曾自己写过好多次的原地反转链表,无不以失败告终,最后不得不在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;
全程就是这么的一气呵成,再也不用去死记硬背了。