长沙 网站设计 公司,做滤芯的网站,做演讲和做演讲视频网站,一个人做网站时间LeetCode 206. 反转链表
题目描述
给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。
示例 1#xff1a;
输入#xff1a;head [1,2,3,4,5]
输出#xff1a;[5,4,3,2,1]示例 2#xff1a;
输入#xff1a;head [1,2]
输出#x…LeetCode 206. 反转链表
题目描述
给你单链表的头节点 head 请你反转链表并返回反转后的链表。
示例 1
输入head [1,2,3,4,5]
输出[5,4,3,2,1]示例 2
输入head [1,2]
输出[2,1]示例 3
输入head []
输出[]Java 实现解法
方法一迭代
/*** 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 curr head;while (curr ! null) {ListNode nextTemp curr.next; // 保存当前节点的下一个节点curr.next prev; // 将当前节点指向前一个节点实现反转prev curr; // 前一个节点前移curr nextTemp; // 当前节点前移}return prev; // 当curr为null时prev就是反转后的头节点}
}方法二递归
class Solution {public ListNode reverseList(ListNode head) {if (head null || head.next null) {return head;}ListNode newHead reverseList(head.next); // 递归反转下一个节点head.next.next head; // 设置下一个节点的next为当前节点实现反转head.next null; // 当前节点的next设置为nullreturn newHead; // 返回新的头节点}
}解题思路 迭代方法 使用三个指针 prev、curr 和 nextTemp 来追踪和修改链表的节点。prev 初始化为 nullcurr 初始化为头节点 head。在循环中首先保存 curr.next 到 nextTemp然后将 curr.next 设置为 prev实现反转。prev 和 curr 都前移直到 curr 为 null此时 prev 就是反转后的头节点。 递归方法 递归的基本情况是当链表为空或只有一个节点时直接返回头节点。在递归调用中我们首先反转下一个节点然后调整当前节点的指针使其指向前一个节点最后返回新的头节点。
这两种方法的时间复杂度都是 O(n)其中 n 是链表的长度。空间复杂度对于迭代方法是 O(1)因为我们只使用了有限的额外空间对于递归方法是 O(n)因为递归调用的栈空间。
注来源leetcode网站
