206-翻转链表.md

206 翻转链表

难度：Easy 原题地址 参考

通常要求翻转链表需要的方法有循环和递归 增加难点就是不使用额外的空间

循环实现

const reverseList = function(head) {
    let [prev, curr] = [null, head];
    while (curr) {
        let tmp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = tmp;
    }
    return prev;
}

简化实现

这个实现就没有开辟新的空间

const reverseList = function(head) {
    let [prev, curr] = [null, head];
    while (curr) {
        [curr.next, prev, curr] = [prev, curr, curr.next];
    }
    return prev;
}

自递归法

这个不太好理解

const reverseList = function (head) {
    if (!head || !head.next) return head;
    let next = head.next; // next 节点，反转后是最后一个节点
    let reverseHead = reverseList(next);
    head.next = null; // 裁剪 head
    head.next = head; // 尾接
    return reverseHead;
}

尾递归法

这个实现方法也很好，reverse 写的很精髓

const reverseList = function (head) {
    return reverse(null, head);
}

function reverse (prev, curr) {
    if (!curr) return prev;
    let tmp = curr.next;
    // prev = tmp; 我还以为这一步是需要的，像写bubble sort 那样，但确实是不需要的
    curr.next = prev;
    return reverse(curr, tmp);
}