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); } }