给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
链表反转是⼀个出现频率特别⾼的算法题,笔者过去这些年⾯试,⾄少遇到过七⼋次。其中更夸张的是曾经两天写 了三次,上午YY,下午⾦⼭云,第⼆天快⼿。链表反转在各⼤⾼频题排名⽹站也⻓期占领前三。⽐如⽜客⽹上这个 No 1 好像已经很久了。所以链表反转是我们学习链表最重要的问题,没有之⼀。 那为什么反转这么重要呢?因为反转链表涉及结点的增加、删除等多种操作,能⾮常有效考察对指针的驾驭能⼒和 思维能⼒。 另外很多题⽬也都要⽤它来做基础, 例如指定区间反转、链表K个⼀组翻转。还有⼀些在内部的某个过程⽤到了反 转,例如两个链表⽣成相加链表。还有⼀种是链表排序的,也是需要移动元素之间的指针,难度与此差不多。接下 来我们就具体看⼀下每个题⽬。
请将这个算法背下来!!!!它太重要了
示例 3:
输入:head = [] 输出:[]
链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000
方法一:迭代 假设存在链表 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)。
方法一:
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;
}
}
方法二:
```java
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 到达链表的最后一个结点 .
```java
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
}
}