反转链表【迭代、递归】

反转一个单链表。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

方法一：迭代

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        /**
         * 思路:存在链表 1 → 2 → 3 → null，我们想要把它改成 null ← 1 ← 2 ← 3。
         * 在遍历列表时，将当前节点的 next 指针改为指向前一个元素。
         * 由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。
         * 在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！
         */
        ListNode prev = null; //定义前位变量
        ListNode curr = head; //定义当前位变量
        ListNode next; //定义后位变量
        while (curr != null) { //移位的过程
            next = curr.next; //为后位变量赋值
            curr.next = prev; //将后位移位，使当前变量指向前位
            prev = curr; //使当前变量指向前位后，重置前位变量
            curr = nextTemp; //使当前变量指向前位后，重置当前位变量
        }
        return prev;
    }
}

复杂度分析

• 时间复杂度：O(n)O(n) 。 假设 nn 是列表的长度，时间复杂度是 O(n)O(n)。
• 空间复杂度：O(1)O(1) 。

方法二：递归

递归版本稍微复杂一些，其关键在于反向工作。假设列表的其余部分已经被反转，现在我该如何反转它前面的部分？假设列表为：n₁ → … → n_k-1 → n_k → n_k+1 → … → n_m → Ø

若从节点 n_k+1 到 n_m 已经被反转，而我们正处于 n_k。

n₁ → … → n_k-1 → n_k → n_k+1 ← … ← n_m

我们希望 n_k+1 的下一个节点指向 n_k。

所以，

n_k.next.next = n_k;

要小心的是 n₁ 的下一个必须指向 Ø 。如果你忽略了这一点，你的链表中可能会产生循环。如果使用大小为 2 的链表测试代码，则可能会捕获此错误。

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) 。 假设 nn 是列表的长度，那么时间复杂度为 O(n)。
• 空间复杂度：O(n) 。 由于使用递归，将会使用隐式栈空间。递归深度可能会达到 n 层。