反转链表
题目描述
输入一个链表,反转链表后,输出新链表的表头。
- 示例1
输入
1 | {1,2,3} |
输出
1 | {3,2,1} |
直观来看对于链表:
反转后
常规解法
- 其实我们本质上是把每个节点的数据之间的指向调整一下
- 通常我们使用preNode(前一个节点),currNode(当前节点),nextNode(当前节点)来实现遍历每个节点修改。最开始preNode指向null,currNode与nextNode指向第一个节点。
现在开始第一个反转:
将nextNode指针指向下一个节点
修改当前指针的方向
方向修改完成,将pre指向当前节点
将当前节点移动到下一个节点上
直到currNode不为null。总结来说preNode用来维持与已经反转好的那部分的关系,nextNode是为了currNode完成方向逆转之后跳到下一个节点,currNode完成方向逆转,承接preNode。想一想如果没有nextNode行不行?
源码(golang)
1 |
|
递归解法
- 以heap为起点进行反转,然后返回新链表的起点元素。
- 注意第一个元素需要做单独处理
源码(golang)
1 |
|