反转链表

[Bulandent]

难度：简单
来源：206. 反转链表

反转一个单链表。

示例:

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

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

思路：

• 定义输出链表 prev
• 顺序遍历链表 head , 将其中的元素移入链表 prev .
• 图解

题解：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // 方法一：迭代实现
    // let prev = null
    // let curr = head
    // while (curr != null) {
    //     let next = curr.next
    //     curr.next = prev
    //     prev = curr
    //     curr = next
    // }
    // return prev

    // 方法二：递归实现
    const reverse = (prev, curr) => {
        if (!curr) {
            return prev
        }
        let next = curr.next
        curr.next = prev
        return reverse(curr, next)
    }
    return reverse(null, head)
};