JAVA练习291- 反转链表

题目概览

给你单链表的头节点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

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

来源：206. 反转链表 - 力扣（LeetCode）

解题分析

方法一：迭代

定义两个变量存储前一个节点和当前节点，遍历时当前节点指向前一个节点即可。

时间复杂度：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 pre = null; ListNode cur = head; while (cur != null) { ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; } return pre; } }

方法二：递归

改造一下方法一的循环即可。

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

/** * 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) { return reverseList(null, head); } public ListNode reverseList(ListNode pre, ListNode cur) { if (cur == null) { return pre; } ListNode temp = cur.next; cur.next = pre; return reverseList(cur, temp); } }