[每日一题] 第二题：反转链表
0 / 0 / 创建于 4年前 /
DRose 的个人博客
题目描述
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000
题解
利用外部空间
先申请一个动态扩容的数组或者容器，比如 ArrayList这样的，
然后不断遍历链表，将链表中的元素添加到这个容器中。
再利用容器自身的 API，反转整个容器，这样就达到反转的效果了。
最后同时遍历容器和链表，将链表的值改为容器的值。
因为此时容器的值为 5 4 3 2 1。
链表按照这个顺序重新被设置一遍，就达到要求了。
空间复杂度
O(N)
双指针法
算法思想
我们申请两个指针，一个指针叫 pre，最初指向 NULL。
第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。
代码
class Solution {
public ListNode reverseList(ListNode head) {
//申请节点，pre和 cur，pre指向null
ListNode pre = null;
ListNode cur = head;
ListNode tmp = null;
while(cur!=null) {
//记录当前节点的下一个节点
tmp = cur.next;
//然后将当前节点指向pre
cur.next = pre;
//pre和cur节点都前进一位
pre = cur;
cur = tmp;
}
return pre;
}
}个人理解
从头遍历链表，修改每个节点的 next 指向的值。
那么一个节点的新的 next 值是什么呢，是它的前一个节点，那么我们把它保存起来即可，用的时候再取出来该值，所以我们定义了 pre 节点。
那么我们应该什么时候给当前节点的 next 节点赋值呢？
我们不能直接执行下面的代码 head.next = pre;，这样是不可以的，形成闭环了。
所以我们有个临时变量 tmp，用来存储当前节点的 next 的值，首先将 head.next 值取出来，然后将 head.next 赋值为 pre，再将 tmp 值赋值给 head，这样我们就下一层循环了。最终获取最后一个节点，就是反转链表的第一个节点，那能否通过 head 节点获取这最后一集个节点呢，因为我们的 head 节点是最后一个节点的 next 值，为 null，所以我们取 head.pre 的值就可以了。
上面的代码用 cur 来代替 head。
递归法
算法思想
递归的两个条件：
终止条件是当前节点或者下一个节点==null
在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句
head.next.next = head
代码
class Solution {
public ListNode reverseList(ListNode head) {
//递归终止条件是当前为空，或者下一个节点为空
if(head==null || head.next==null) {
return head;
}
//这里的cur就是最后一个节点
ListNode cur = reverseList(head.next);
//这里请配合动画演示理解
//如果链表是 1->2->3->4->5，那么此时的cur就是5
//而head是4，head的下一个是5，下下一个是空
//所以head.next.next 就是5->4
head.next.next = head;
//防止链表循环，需要将head.next设置为空
head.next = null;
//每层递归函数都返回cur，也就是最后一个节点
return cur;
}
}个人理解
终止条件为什么有两个？
分别对应着两种情况：
- 链表为空，需要判断
head==null - 正常链表，需要判断
head.next==null
head.next.next = head 怎么理解？**
head.next 是当前节点的下一个节点，这个节点的 next 值就是反过来嘛，就是 head
head.next = null 是什么意思？**
为了防止闭环。
为什么会返回 cur？
因为 cur 是最后一层递归返回的值，也就是最后一个节点，也是反转链表的第一个节点，所以我们返回这个节点即可。
题目出处
作者：wang_ni_ma
链接：leetcode-cn.com/problems/fan-zhuan...
来源：力扣（LeetCode）
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号