$$\color{Red}{反转链表}$$

我的网站=> 分享了我关于前后端的各种知识和生活美食~

我于Acwing平台分享的零散刷的各种各样的题

给定单链表的头节点 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

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

迭代

双指针，我们要做的是每次让后面的节点指向前面的节点，那么开局需要第一个指针指向第一个节点，第二个指向第二个节点，为了防止为空，提前特判一下为空的情况直接返回空【均为空】，或者返回头节点【只有一个节点】

然后需要让后一个节点指向前一个，然后两个指针往后各移动一位，这里其实能发现，如果是头节点，就会出现头节点又指回第二个节点，就无限循环了，所以需要头节点指向空，这里可以在循环特判，也可以事后特判，反正我们没有改动 head 指针指向的地址。

那么只剩下末尾边界了，考虑一下，显然第二个指针不能指向空，不能让空地址指向前一个节点，自然第一个指针在此限制也没机会指空，最后返回第一个指针指向的节点即可。

然后只剩下细节移动位置的情况了，要满足不会出现断节点。后一个指向前一个节点的时候，就没法移动位置，所以只能多开一个变量，提前把第二个指针的节点的下一个节点存一下，然后反转之后，就能移动位置了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode cur = head;
        ListNode sentinel = cur.next;
        while (sentinel != null) {
            ListNode temp = sentinel.next;
            sentinel.next = cur;
            cur = sentinel;
            sentinel = temp;
        }
        head.next = null;
        return cur;
    }
}

递归

递归我们需要考虑一个问题，首先返回值，需要返回的是反转之后的头，即正向的尾巴，故每次递归最后返回当前链表的尾部。

存在一直递归的情况，故尾巴节点的位置不能变，那只能是前面的节点减少了【递归形参是头节点，故如果变尾巴，每个递归都得迭代遍历到尾，直觉复杂度太高也不科学】

故递归每次都是缩短前面的节点，然后递归之后返回末尾，然后递归的小链表指向前面的未进入递归的部分。

显然缩短一个就行，那递归到底就是尾巴节点，我们要对尾巴做什么操作？

首先它以后得作为头节点，所以应该是返回值，但是如果是返回值，头会动态变化，故我们需要提前存下来最内层头的地址，然后返回。

那么递归的深层的头，其实是缩短之后的头，我们只需要让这个头的下一个节点指向自己，然后当前头指向空【不用担心它之后怎么指向前面的节点的问题，更外层的递归，头节点在它左边，指向当前头，会让它又指回外层的头的，这么做的好处是，最后保证了最开始的头指向空，同时把链表反转了】

同时我们意识到，如果递归到只有一个节点，它的尾巴就是头【同一个节点】，直接返回即可，不需要做指向操作。而且还要放在递归函数之前，递归尾巴节点的下个节点，相当于递归 null，直接空指针异常。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode tail = reverseList(head.next);
        head.next.next =  head;
        head.next = null;
        return tail;
    }
}