大家好！我是曾续缘💗

今天是《LeetCode 热题 100》系列

发车第 23 天

链表第 2 题

❤️点赞 👍 收藏 ⭐再看，养成习惯

反转链表 给你单链表的头节点 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. 初始化三个指针：prev指向前一个节点，current指向当前节点，next指向当前节点的下一个节点。

2. 遍历链表，当current不为null时执行以下操作：

   • 将current.next指向前一个节点，即将当前节点的指针反转。
   • 更新指针，将prev指向当前节点，将current指向下一个节点，将next指向下一个节点的下一个节点。

3. 遍历结束后，返回新的头节点，即原链表的尾节点。

递归法可以通过递归地调用函数来实现链表的反转。

1. 如果链表为空或只包含一个节点，则直接返回该链表。
2. 假设传入的链表的头节点为head，递归调用函数reverseList(head.next)来反转以头节点之后的链表。
3. 将头节点的下一个节点的next指向头节点，将头节点的next指向null，完成头节点的反转。
4. 返回反转后的新头节点。

Code

递归法

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

迭代法

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;

        while (current != null) {
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        return prev;
    }

}