1 题目描述

1. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

链表反转是⼀个出现频率特别⾼的算法题，笔者过去这些年⾯试，⾄少遇到过七⼋次。其中更夸张的是曾经两天写
了三次，上午YY，下午⾦⼭云，第⼆天快⼿。链表反转在各⼤⾼频题排名⽹站也⻓期占领前三。⽐如⽜客⽹上这个
No 1 好像已经很久了。所以链表反转是我们学习链表最重要的问题，没有之⼀。
那为什么反转这么重要呢？因为反转链表涉及结点的增加、删除等多种操作，能⾮常有效考察对指针的驾驭能⼒和
思维能⼒。
另外很多题⽬也都要⽤它来做基础， 例如指定区间反转、链表K个⼀组翻转。还有⼀些在内部的某个过程⽤到了反
转，例如两个链表⽣成相加链表。还有⼀种是链表排序的，也是需要移动元素之间的指针，难度与此差不多。接下
来我们就具体看⼀下每个题⽬。

请将这个算法背下来！！！！它太重要了

2 题目示例

示例 3：

输入：head = []
输出：[]

3 题目提示

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

4 思路

方法一：迭代
假设存在链表 1 \rightarrow 2 \rightarrow 3 \rightarrow \varnothing1→2→3→∅，我们想要把它改成 \varnothing \leftarrow 1 \leftarrow 2 \leftarrow 3∅←1←2←3。

在遍历列表时，将当前节点的 \textit{next}next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！

复杂度分析

时间复杂度：O(n)O(n)，假设 nn 是列表的长度，时间复杂度是 O(n)O(n)。
空间复杂度：O(1)O(1)。

5 我的答案

方法一：

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

方法二：

class Solution {

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

}

最后再用双指针做一遍：

妖魔化的双指针

• 原链表的头结点就是反转之后链表的尾结点，使用 headhead 标记 .
• 定义指针 curcur，初始化为 headhead .
• 每次都让 headhead 下一个结点的 nextnext 指向 curcur ，实现一次局部反转
• 局部反转完成之后，curcur 和 headhead 的 nextnext 指针同时 往前移动一个位置
• 循环上述过程，直至 curcur 到达链表的最后一个结点 .

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null)
        {
            ListNode t = cur.next;  //保留cur的后继节点
            cur.next = pre;         //cur指向其前驱节点
            pre = cur;
            cur = t;
        }
        return pre;                    //最后返回pre
    }
}