206. 反转链表

[FE-Sadhu]

题目

思路一: 栈
利用栈先进后出的特性，先在一遍迭代中存每个 node 到栈里，再迭代栈，依次构建新链表。

代码实现:

var reverseList = function(head) {
    const stack = [];
    while(head) {
        stack.push(head);
        head = head.next;
    }
    const dummy = new ListNode(null);
    let helper = dummy;
    while(stack.length) {
        helper.next = stack.pop();
        helper = helper.next;
    }
    helper.next = null;  // 记得赋 null，不然循环引用
    return dummy.next;

    let helper = null;
    while (head) {
        const next = head.next;
        head.next = helper;
        helper = head;
        head = next;
    }
    return helper;
};

时间复杂度: O(n);
空间复杂度: O(n);

思路二：递归
定义： reverseList 的返回值就是反转后的链表的头节点。
出口： 当 reverseList 的参数传入的节点指向 null 时，证明链表只有一个节点，反转与否都是它，直接返回这个节点即可。

代码实现:

var reverseList = function(head) {
     if (!head || !head.next) {
         return head;
     }
     const reversed = reverseList(head.next);
     head.next.next = head;
     head.next = null;  // 记得赋 null，不然循环引用
     return reversed;
};
时间复杂度: O(n) n 取决于递归的层数
空间复杂度: O(n);

思路三：
一次遍历中动态修改原本的链表以及构建新链表。

代码实现:

var reverseList = function(head) {
    let helper = null;
    while (head) {
        const next = head.next;  // 缓存旧链表的下一个节点
        head.next = helper;  // 当前节点指向新链表的头节点
        helper = head; // 改变新链表的头节点
        head = next; // 改变旧链表为下一个节点
    }
    return helper;  // 返回新链表
};

时间复杂度: O(n);
空间复杂度: O(1);