203. 移除链表元素

方法1：遍历

/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function (head, val) {
  let root = cur = new ListNode(0, head);
  while (cur.next) {
    if (cur.next.val === val) {
      cur.next = cur.next.next;
    } else {
      cur = cur.next;
    }
  };
  return root.next;
};

【解题思路】

• 遍历链表

  • 若链表当前节点的下一个节点的值与 val 相等，那么将下一个节点重新赋值为当前节点的 下下 个节点（即“删除链表上，当前节点的下一个节点。）
  • 否则，直接赋值为下一个节点

【注意点】

• 在链表的表头添加一个根节点 root，令 root.next === head
• 定义一个变量 cur，初始值为 root，表示当前节点。

• 最后返回的是 root.next 而非 cur.next。

  • cur 用于实现功能，它的指向会变，但是 root 的指向始终不变，所以最终返回的是 root.next

【思考】

为什么要使用当前节点的下一个节点的 val 值去判断，不直接使用当前节点的 val 去判断？

试想一下，如果使用当前节点来做判断的话，若当前节点的 val 不满足要求，也就是与传入的 val 值不相等（cur.val !== val），那么，这种情况下是没问题的，直接令 cur = cur.next; 继续判断下一个节点就好。

但是，如果当前节点的值满足要求的话（cur.val === val），会出现无法找到当前节点的上一个节点的问题，进而导致当前节点无法被删除。因为我们需要将上一个节点（cur.pre）的 next 指向当前节点的下一个节点 cur.next，以此来删除当前这个需要被删除的节点。

方法2：递归

/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function (head, val) {
  if(head === null){
    return head;
  }
  head.next = removeElements(head.next, val);
  return head.val === val ? head.next : head;
};

【解题思路】

先找出口：若当前节点是 null，那么意味着 “递” 到了最后一个节点，此时可以开始 “归” 了。

• 递

  • 递的过程，啥也不做，就是将当前指针 “递” 到最后一个节点

• 归

  • 归的过程，是在 “递” 的过程结束之后，意味着：“归” 也是从最后一个节点开始的；

  • 归的过程，好比从后往前依次遍历各节点，对于遍历到的节点，需要判断是归并当前节点还是当前节点的下一个节点。

    • 若发现当前节点的 val 值与传入的 val 值相同，那么将当前节点的下一个节点归并；（意味着删除当前这个节点）
    • 若发现当前节点的 val 值与传入的 val 值不同，那么直接将当前节点归并；

测试示例

function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}

const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(6);
const node4 = new ListNode(3);
const node5 = new ListNode(4);
const node6 = new ListNode(5);
const node7 = new ListNode(6);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = node7;

function bianliNodeList(node) {
  if (node === null) {
    return;
  }
  console.log(node.val);
  bianliNodeList(node.next);
}

// bianliNodeList(node1);

/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function (head, val) {
  // ...
};

const root = removeElements(node1, 6);
bianliNodeList(root); // 1 2 3 4 5

bug

/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function (head, val) {
  let cur = new ListNode(0, head);
  while (cur.next) {
    if (cur.next.val === val) {
      cur.next = cur.next.next;
      continue;
    } else {
      cur = cur.next;
    }
  }
  return head;
};

由于表头 head 也是有可能会变的，即：它也有可能是需要被删除的。所以，这么写的话，就会存在一个隐患，像下面这样的测试示例会通不过，因为表头 head 也需要被删掉。

输入：[7, 7, 7, 7] 7
输出：[]
实际输出：7 7 7 7

程序执行完后： 0 ==> null

206. 反转链表

方法1 「递归算法」

var reverseList = function (head) {
  // 链表的长度为0或1 直接返回
  if (head === null || head.next === null) return head;
  if (head.next.next === null) {
    const lastNode = head.next;
    head.next.next = head;
    head.next = null;
    return lastNode;
  }
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
};

注解

当链表的长度小于2时，直接将表头节点返回。否则，走以下逻辑，核心其实就俩字：“递”、“归”。

• 递

递的过程，其实就是指针后移的过程。用代码来表示就是 reverseList 不断调用自身，每次调用都传入当前节点的下一个节点，直到找到倒数第二个节点为止。其实，找到倒数第二个节点，也就意味着找到了最后一个节点，然后每次 return 都将最后一个节点给返回，这样就能确保我们最终返回的必然是原链表的尾节点，即：新链表的表头节点。

var reverseList = (head) => {
  if (head.next.next === null) {
    const lastNode = head.next;
    // 归
    return lastNode;
  }
  const lastNode = reverseList(head.next);
  // 归
  return lastNode;
}

递，我们找到了最后一个节点，并且将指针移到了倒数第二个节点的位置。

• 归

归的过程，其实就是指针回指的过程。在回指的过程中，还得干下面两件事儿。

// 1. 当前指针所指节点 head 的下一个节点 head.next 的指向 head.next.next，改为指向当前节点 head。
head.next.next = head;
// 2. 当前节点 head 指向 head.next 空 null。
head.next = null;

不断回归，直到指针回指到头。

方法2 「循环」

var reverseList = function (head) {
  let pre = null, cur = head;
  while (cur) {
    const nextNode = cur.next;
    cur.next = pre;
    pre = cur;
    cur = nextNode;
  }
  return pre;
}

注解

提前准备好一个空节点 「pre」，它的位置始终在当前遍历到的节点「cur」之前。从头到尾依次遍历各个节点，每遍历到一个节点，就将该节点回指，然后同时向后移动 pre 和 cur。

278. 第一个错误的版本

1. 暴力解法

var solution = function (isBadVersion) {
  return function (n) {
    for (let i = 1; i <= n; i ++) {
      if (isBadVersion(i)) return i;
    }
  };
};

直接将所有成员都遍历一遍来查找，从最小的开始。

2. 二分查找

var solution = function (isBadVersion) {
  return function (n) {
    let left = 1,
      right = n,
      mid = left + Math.floor((right - left) / 2);
    while (left <= right) {
      if (isBadVersion(mid)) { // 当前版本有错
        right = mid - 1;
        if (!isBadVersion(right)) { // 并且，当前版本的前一个版本没错
          return mid;
        }
      } else { // 当前版本没错
        left = mid + 1;
      }
      mid = left + Math.floor((right - left) / 2);
    }
  };
};

解题思路：同 704. 二分查找，不过得加一个判断，当找到错误的成员之后，必须确保该错误成员的左侧（前一个）成员必须是正确的，这样才能确保当前找到的这个错误成员是第一个出错的成员。

小结

本题是 学习计划 [算法] 第一天的第二题，在通过第一题 704. 二分查找 之后，再来写这道题，感觉简单多了。

283. 移动零

方法1 「双指针」

var moveZeroes = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) continue;
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] === 0) continue;
      [nums[i], nums[j]] = [nums[j], nums[i]];
      break;
    }
  }
};