最 简单 详细 易懂的反转链

思想:

把原始链表节点一个个切下来,粘到左边的新链表上(左链表初始为空)

时间复杂度O(n),空间复杂度O(1)

链表变化过程:
node1->node2->node3-node4

一个个切下粘到左边

node1 … node2->node3->node4

node1<-node2 …. node3->node4

node1<-node2<-node3 …. node4

node1<-node2<-node3<-node4

代码思路: 循环切下每个节点,依次粘到左侧链表中

​ 1. 保存当前被切节点的next, 即切后原始链表的头结点,(4)里迭代下一个节点要用

2. 切下的节点粘贴到左边

3. 左边链表增加节点后更新头结点

4. 迭代下一个被切的节点, 即原始链表的头结点

(1)中保存next目的是为了(4)中用,如果不保存,经过二操作后cur->next节点就不是原来cur->next节点了)

递归版中3和4步和在一起了,

链表定义

 

循环版本代码

 

递归版
采用尾递归,翻转完成时候直接返回左边链表即可