一行代码引起的思考

Author Avatar
Peipei Wong 3月 12, 2019
  • 在其它设备中阅读本文章

leetcode的92题是一道反转从m到n的链表的题目。说起链表,就想起来刚接触链表的时候,随意改变指向的兴奋感。第一门接触的语言是C++,不过想要使用C++去尝试解题的时候,发现我之前接触的已经过时了(用c写链表比js舒服呀),还是拿着js来吧。

回到题目,我在想当m等于1的时候,算不算特殊情况?为了统一来说,还是不当做特殊情况,于是我决定,只拿出m开始的链表进行操作,最后再接上。

下面是我第一次解法:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */
var reverseBetween = function (head, m, n) {
  if(m === n) return head;

  let startPrevNode = null;
  let startNode = null;
  let currentNode = head;
  let reverseHeadNode = null;
  let index = 1;

  while(index < m) {
    startPrevNode = currentNode;
    currentNode = currentNode.next;
    index++;
  }
  reverseHeadNode = startNode = currentNode;

  while(index < n) {
    index++;
    currentNode = currentNode.next;

    startNode.next = currentNode.next;
    currentNode.next = reverseHeadNode;
    reverseHeadNode = currentNode;
    // console.log('reverseHeadNode', reverseHeadNode)
    currentNode = startNode;
  }

  if (startPrevNode) {
    startPrevNode.next = reverseHeadNode;
    return head;
  } else {
    return reverseHeadNode;
  }
};

答案通过了,但是我的速度只超过了40%的人,内存消耗只少于7%的人,这结果真是沮丧。于是,我开始缕缕算法,发现每次移动的元素都是startNode后面的元素,这个时候,我只需要知道startNode,而不需要每次保存currentNode的值。所以我尝试改了第二个while中的操作。

while(index < n) {
  index++;
  currentNode = startNode.next;

  startNode.next = currentNode.next;
  currentNode.next = reverseHeadNode;
  reverseHeadNode = currentNode;
}

更改之后,少了一次赋值操作,但是有了很大的提升,速度超了86%, 内存消耗少了15%,算起来效率提升了两倍,算法给人的想象真的是无穷的。我只是删除了一行代码,没想到会有这样的结果。同时最近看的“高性能的javascript”,尽管书出来很多年了,但是其中还是有很多的精髓的地方。

算法使我的code更美,更快,更小!