876. 链表的中间结点

1. 暴力解法

var middleNode = function(head) {
  // 获取到链表的总长度
  let len = 1,
  root = head;
  while (head.next) {
    len ++;
    head = head.next;
  }
  // 找中点
  for (let i = 0; i < Math.floor(len / 2); i++) {
    root = root.next;
  }
  return root;
};

2. 双指针

// 快慢指针
var middleNode = function(head) {
  let slow = fast = head;
  while (fast.next !== null && fast.next.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
};

看大神写的图解，是真的很直观，直接了当，没废话。。。。

需要注意的点就是指针前进的条件。

点击查看参考的题解

881. 救生艇

方法1 「贪心」

var numRescueBoats = function(people, limit) {
  people.sort((p1, p2) => p1 - p2); // 升序
  let light = 0, heavy = people.length - 1, ans = 0;
  while (light <= heavy) {
    if (people[light] + people[heavy] <= limit) {
      light++;
      heavy--;
    } else {
      heavy--;
    }
    ans++;
  }
  return ans;
};

注解

核心：能装俩，绝不装一。

先将乘客按照体重升序排序，站在最前面的是最轻的，站在最后面的是最重的。每次都先让最重的上艇，若此时最轻的还能上，则上；不能上，则开艇。

思考

• 为什么最重和最轻搭，是最优解呢？

比如说，最重的是 7，最轻的是 1；那么 7 和 3 搭显然是要比 7 和 1 搭更“贪心”，看似更能充分地利用资源。但是，我们不妨换一种思维方式来看待这个问题。

更充分的利用资源 == 尽可能少的浪费资源

首先，最轻的 2 必然是要走的，那么它如果能和当前最重的一起走，对资源的浪费是最少的，以此类推。所以说最重和最轻的搭，是最优解。

会发现，本题的最优解不唯一。

• 3 + 7 | 5 + 5 | 2 => 浪费的资源 0 + 0 + 8 => 8

• 7 + 2 | 5 + 3 | 5 => 浪费的资源 1 + 2 + 5 => 8

• … 等等

但是这些最优解都有一个共同点，浪费的资源量都是一样的。