每日算法题：反转链表

题目（反转链表）

给定一个单链表的头节点 head，请将链表反转，并返回反转后的链表的头节点。

例如，给定链表 1 -> 2 -> 3 -> 4 -> 5，反转后的链表应为 5 -> 4 -> 3 -> 2 -> 1。

请编写一个函数 reverseList，实现上述功能。

函数签名如下：

public ListNode reverseList(ListNode head) {
    // TODO: 实现函数体
}

其中，ListNode 是一个单链表节点的定义：

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

提示：

• 你可以迭代或递归地反转链表。
• 你能否用 O(1) 的空间复杂度解决此问题？

祝你好运！

解题思路和答案

链表的反转是一个经典的问题，有两种常见的解法：迭代和递归。

迭代法的思路是：从头节点开始，依次将每个节点的 next 指针指向它的前一个节点，最后返回新链表的头节点。

递归法的思路是：先递归地反转子链表，然后将当前节点的 next 指针指向前一个节点，最后返回新链表的头节点。

具体实现见下面的答案和代码。

答案：

以下是迭代法的实现：

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

以下是递归法的实现：

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

这两种方法的时间复杂度都是 O(n)，其中 n 是链表的长度。迭代法的空间复杂度是 O(1)，递归法的空间复杂度是 O(n)，因为递归需要使用系统栈空间。

这道题还有一个进阶问题：如何用 O(1) 的空间复杂度解决此问题？可以使用迭代法和递归法的变形解法，这里不再赘述。

完整的 Java 代码如下：

public class Solution {
    public ListNode reverseList(ListNode head) {
        // 迭代法
        // ListNode prev = null;
        // ListNode curr = head;
        // while (curr != null) {
        //     ListNode next = curr.next;
        //     curr.next = prev;
        //     prev = curr;
        //     curr = next;
        // }
        // return prev;

        // 递归法
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}

如果需要了解完整的思路和新奇的例子，可以去力扣增强自己的算法实力。