1、剑指 Offer 24. 反转链表
目录
一、题目
剑指 Offer 24. 反转链表 难度简单
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000
注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/
二、解法
2.1、遍历法（双指针）
核心思想：
在访问各节点时修改其 next 引用指向。在此过程中，可借助辅助变量（指针）来保存当前节点的 next ，以此为基础遍历整个链表。
复杂度分析：
- 时间复杂度 O(N)：遍历链表使用线性大小时间。
- 空间复杂度 O(1)： 变量
pre和cur使用常数大小额外空间。
代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 上一个节点
ListNode prev = null;
// 当前节点
ListNode cursor = head;
while (cursor != null) {
// 辅助变量 next , 用以保存当前节点指向的下一个结点.
ListNode next = cursor.next;
// 让当前节点
cursor.next = prev;
// 循环处理的关键, 让当前节点作为 prev , 让辅助变量 next 作为当节点, 并进入下一个循环
prev = cursor;
cursor = next;
}
// 当 cursor 为 null 时, 整个链表已经被反转过来了
return prev;
}
}
2.2、递归法
核心思想：
使用递归法遍历链表，当越过尾节点后终止递归，在回溯时修改各节点的 next 引用指向。
复杂度分析：
- 时间复杂度 O(N)：遍历链表使用线性大小时间。
- 空间复杂度 O(N)： 遍历链表的递归深度达到 N ，系统使用 O(N) 大小额外空间。
代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 调用递归并返回
return recur(head, null);
}
private ListNode recur(ListNode cur, ListNode pre) {
System.out.println(cur);
// 当 cur 为 null 时, pre 指向尾结点, 此时将 pre 作为反转链表的表头，开始回溯.
if (cur == null) return pre;
// 递归调用函数, 此时将 root 看作是一个已经被反转过的链表的表头.
ListNode root = recur(cur.next, cur);
// 将当前节点的 next 指向上一个节点，也就是 prev
cur.next = pre;
// 将反转过的链表的表头传递返回给上一级
return root;
}
}