【力扣】206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2
输入：head = [1,2]
输出：[2,1]
示例 3
输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
题解
方法一：迭代
思想：将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;while (cur != null) {// 记录当前节点的下一个节点ListNode tmp = cur.next;// 然后将当前节点指向precur.next = pre;// pre和cur节点都前进一位pre = cur;cur = tmp;}return pre;}
}
方法二：递归
递归的重要两步：
- 终止条件：
//递归终止条件是当前为空，或者下一个节点为空
if(head==null || head.next==null) {return head;
}
- 在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句
head.next.next = head
// 其实就是 head 的下一个节点指向head
递归函数中每次返回的 cur 其实只是最后一个节点，在递归函数内部，改变的是当前节点的指向。
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->4head.next.next = head;//防止链表循环，需要将head.next设置为空，断掉head.next = null;//每层递归函数都返回cur，也就是最后一个节点return cur;}
}
