Leetcode - 反转链表

反转一个单链表。

示例:

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

链表的结构如下：

    const head = {
      val: "a",
      next: {
        val: "b",
        next: {
          val: "c",
          next: null,
        },
      },
    };

用while循环

我首先想到的就是这个

var reverseList = function(head) {
    
    let currentNode = head , cloneNode = null;
    while(currentNode !== null){
        cloneNode = {
            val : currentNode.val,
            next : cloneNode
        }
        currentNode = currentNode.next;
    }
    return cloneNode;
};

cloneNode = null 初始化为null是个好习惯，不然无法通过测试。

从头开始遍历链表，后面的节点放在前一个节点的前面

上述解法创造了一个新的链表，能否利用已有的节点呢？
看看下面递归的解法，平时被病垢的引用传值在这里大放异彩！

递归解法

这是其他人的解法

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

每一次递归head形参的值都是不一样的
第一次:a b c null
第二次:b c null
第三次:c null
返回到第二次:这时p指向的c与hedad形参b c 中的c是同一个引用

head.next.next = head; 

head=>b c b c b ...
p => c b c b c b...

head.next = null ;

head=> b null
p => c b null
返回到第一次:此时head形参已变为a b null, 这时p指向的b与hedad形参a b null 中的b是同一个引用。

head.next.next = head;

head => a b a b a b ...
p => c b a b a b..

head.next = null;

head=> a null
p=> c b a null
一开始传入的参数head也支离破碎了，可不可以保留原本的结构呢？

尝试使用潜复制

    var reverseList = function(head) {
      if (head == null) return null;
      if (head.next == null) {
        return {
          ...head,
        };
      }

      let p = reverseList(head.next);
      let node = { ...head };
      node.next = null;
      p.next = node;

      return p;
    };

结果为 c a null

第一次:head=>a b c null
第二次:head=>b c null
第三次:head=>c null
返回到第二次:
node=> b c null

node.next = null;

node => b null

p.next = node;

p => c b null
返回到第一次：
node=>a b c null

node.next = null;

node=>a null

p.next = node;

p=> c a null
直接对p操作，当节点数大于1的时候会出现问题

记录最后一个节点的引用

    var reverseList = function(head) {
      if (head == null) return null;
      if (head.next == null) {
        let node = {
          ...head,
        };
        return [node, node];
      }

      let [p, lastNode] = reverseList(head.next);
      let node = { ...head };
      node.next = null;
      lastNode.next = node;

      return [p, node];
    };

lastNode 存储p最后一个节点的引用
每次通过它来链接上一个节点

上述解法有两个问题：
1.head == null时没有做处理
2.lastNode 在倒序完成时没必要返回
优化如下:

    var reverseList = function(head) {
      var deal = function(innerHead) {
        if (innerHead == null) return [null];
        if (innerHead.next == null) {
          let node = {
            ...innerHead,
          };
          return [node, node];
        }

        let [p, lastNode] = deal(innerHead.next);
        let node = { ...innerHead };
        node.next = null;
        lastNode.next = node;

        return [p, node];
      };
      let [result] = deal(head);
      return result;
    };

在外面包裹了一层函数。
用箭头函数会更简练一些。

完