【LeetCode】剑指 Offer 24. 反转链表 p142 -- Java Version

题目链接：https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/submissions/

1. 题目介绍（24. 反转链表）

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

【测试用例】：
示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

【条件约束】：

限制：

• 0 <= 节点个数 <= 5000

【相关题目】：

注意：本题与主站 206. 反转链表 题目相同。

2. 题解

2.1 原书题解 双指针+临时指针（记录cur.next）-- O(n)

时间复杂度O(n)，空间复杂度O(1)

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode reverseList(ListNode head) {// 判空：// 1. 如果头节点为空，那么返回空// 2. 如果头节点的下一个节点为空，那么返回头节点if (head == null || head.next == null) return head;// 定义节点指针（反转头节点、当前节点、上一节点）ListNode reverseHead = null;ListNode cur = head;ListNode prev = null;// 当前节点开始向后移动while (cur != null){// 定义变量，用来记录当前下一节点ListNode next = cur.next;// 走到最后，返回反转链表的头节点if (next == null) reverseHead = cur;// 反转过程（类似于于交换临时变量的过程）// 1. 当前节点的下一节点指向前一节点// 2. 前一节点指向当前节点// 3. 当前节点则指向提前记录好的下一节点cur.next = prev;prev = cur;cur = next;  }return reverseHead;}
}

2.2 递归 – O(n)

时间复杂度O(n)，空间复杂度O(n)

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

2.3 迭代 – O(n)

时间复杂度O(n)，空间复杂度O(1)

class Solution {public ListNode reverseList(ListNode head) {ListNode cur = head, pre = null;while(cur != null) {ListNode tmp = cur.next; // 暂存后继节点 cur.nextcur.next = pre;          // 修改 next 引用指向pre = cur;               // pre 暂存 curcur = tmp;               // cur 访问下一节点}return pre;}
}

3. 参考资料

[1] 剑指 Offer 24. 反转链表（迭代 / 递归，清晰图解）-- 2.3 迭代法参考 & 2.2 递归图源
[2] 反转链表 – 2.2 递归法参考