题目
反转链表给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000]
-5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
题解
解题分析
解题思路
- 迭代的方式处理
- 假设链表数据为
1->2->3->end, 我们需要把它修改为end->3->2-1。
- 在遍历的时候，将当前的
next指针修改为指向前一个节点。由于节点没有引用前一个节点，必须事先存储前一个节点。在修改引用之前，还需要存储后一个节点，最后执行完成后返回新的头节点。
- 需要经历一轮循环才能完成反转。
复杂度
时间复杂度 O(N)
空间复杂度 O(1)
解题代码
题解代码如下（代码中有详细的注释说明）：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null ; ListNode curr = head; // 直接迭代反转 while(curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } }
提交后反馈结果（由于该题目没有进行优化，性能一般）：
- 另外一种解法（递归）, 核心代码就是
ead.next.next = head。
class Solution { public ListNode reverseList(ListNode head) { // 如果头为空，或者只有一个节点 if (head == null || head.next == null) { // 递归出口 return head; } // 递归调用 ListNode newHead = reverseList(head.next); // 这里很难理解本质就是将 // 1->2->end 转换为 end->2->1 head.next.next = head; // 防止出现环 head.next = null; return newHead; } }
