HomeArchivesCategoriesLabelMomentsPhotosLinkAbout

LeetCode 206. 反转链表

学习
51
0
0
2022-04-28
LeetCode 206. 反转链表


LeetCode 206. 反转链表

问题描述

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

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

思路

方法一：递归

使用递归来反转链表。递归的终止条件是链表为空或只有一个节点，此时直接返回头节点。在递归的过程中，每次都将当前节点的下一个节点指向自己，实现链表反转。

方法二：迭代和双指针

使用双指针和迭代的方法来反转链表。定义两个指针 prev 和 curr，初始时 prev 为空，curr 指向链表的头节点。迭代过程中，将 curr 的 next 指针指向 prev，然后将 prev 和 curr 向后移动，直到 curr 遍历到链表的末尾，此时 prev 指向反转后的链表的头节点。

代码实现（Java）

方法一：递归

class Solution {
    public ListNode reverseList(ListNode head) {
        // 递归终止条件
        if (head == null || head.next == null) {
            return head;
        }
        // 先将以 head.next 为头节点的链表进行反转，得到 newHead
        ListNode newHead = reverseList(head.next);
        // 将 head.next.next 指向 head，实现链表反转
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

方法二：迭代和双指针

class Solution {
    public ListNode reverseList(ListNode head) {
        // prev 指向反转后的头结点，初始值为 null
        ListNode prev = null;
        // curr 指向待反转部分的头节点，初始值为 head
        ListNode curr = head;
        while (curr != null) {
            // 使用 next 记录当前节点 curr 的下一个节点
            ListNode next = curr.next;
            // 将 curr 的 next 指针指向 prev，实现链表反转
            curr.next = prev;
            // curr 和 prev 向后移动
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

总结

本题的解法有多种选择，可以根据需要和题目要求选择合适的方法。希望这个解题思路对你有所帮助。

#LeetCode 9