leetcode hot100 之【LeetCode 206. 反转链表】 java实现

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 初始化为 null，curr 初始化为头节点 head。
  • 在循环中，首先保存 curr.next 到 nextTemp，然后将 curr.next 设置为 prev，实现反转。
  • prev 和 curr 都前移，直到 curr 为 null，此时 prev 就是反转后的头节点。

• 递归方法：

  • 递归的基本情况是当链表为空或只有一个节点时，直接返回头节点。
  • 在递归调用中，我们首先反转下一个节点，然后调整当前节点的指针，使其指向前一个节点，最后返回新的头节点。

这两种方法的时间复杂度都是 O(n)，其中 n 是链表的长度。空间复杂度对于迭代方法是 O(1)，因为我们只使用了有限的额外空间；对于递归方法是 O(n)，因为递归调用的栈空间。

注：来源leetcode网站