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
}
}
