【力扣】206. 反转链表 ＜链表指针＞

【力扣】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;}
}