(链表) LeetCode206. 反转链表

题目：
反转一个单链表。

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

方法一 迭代
时间复杂度：O(n)
空间复杂度： O(1)

var reverseList = function(head) {
    let prev = null;
    let curr = head;
    while (curr != null) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

方法二：递归

n1 →...→ nk−1 → nk → nk+1 ←...←nm

我们希望 nk+1的下一个节点指向nk，所以

nk.next.next = nk

要小心的是n的下一个必须指向null

时间复杂度：O(n)
空间复杂度： O(n)

var reverseList = function(head) {
    if (head == null || head.next == null) return head;
    let p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}