求链表中间节点

判断回文链表

请判断一个单链表是否为回文链表。

示例1:

输入: 1->2
输出: false

示例2:

输入: 1->2->2->1
输出: true

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源: LeetCode第234题

思路分析

这一题如果不考虑性能的限制，其实是非常简单的。但考虑到 O(n) 时间复杂度和 O(1) 空间复杂度，恐怕就值得停下来好好想想了。

题目的要求是单链表，没有办法访问前面的节点，那我们只得另辟蹊径:

找到链表中点，然后将后半部分反转，就可以依次比较得出结论了。下面我们来实现一波。

代码实现

其实关键部分的代码就是找中点了。先亮剑:

let dummyHead = slow = fast = new ListNode();
dummyHead.next = head;
// 注意，找中点
while(fast && fast.next) {
  slow = slow.next;
  fast = fast.next.next;
}

你可能会纳闷了，为什么边界要设成这样？

我们不妨来分析一下，分链表节点个数为奇数和偶数的时候分别讨论。对于 fast 为空和fast.next为空两个条件，在奇数的情况下，总是 fast为空先出现，偶数的情况下，总是fast.next先出现.

也就是说: 一旦fast为空, 链表节点个数一定为奇数，否则为偶数。因此两种情况可以合并来讨论，当 fast 为空或者 fast.next 为空，循环就可以终止了。

完整实现如下:

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
  // 交换链表的两项（反转列表）
  let reverse = (pre, cur) => {
    if (!cur) {
      return pre;
    }
    let next = cur.next;
    cur.next = pre;
    return reverse(cur, next);
  }
  let dummyHead = slow = fast = new ListNode();
  dummyHead.next = head;
  // 注意，找中点,
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let next = slow.next;
  slow.next = null;
  let newStart = reverse(null, next);
  for (let p = head, newP = newStart; newP != null; p = p.next, newP = newP.next) {
    if (p.val != newP.val) {
      return false;
    }
  }
  return true;
};

栈和队列

有效括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例:

输入: "()"
输出: true

来源: LeetCode第20题

代码实现

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  let stack = [];
  for(let i = 0; i < s.length; i++) {
    let ch = s.charAt(i);
    if(ch == '(' || ch == '[' || ch == '{') {
      stack.push(ch);
    }
    if(!stack.length) {
      return false;
    }
    if(ch == ')' && stack.pop() !== '(') {
      return false;
    }
    if(ch == ']' && stack.pop() !== '[' ) {
      return false;
    }
    if(ch == '}' && stack.pop() !== '{') {
      return false;
    }
  }
  return stack.length === 0;
};

多维数组 flatten

将多维数组转化为一维数组。广度优先遍历+递归。

示例:

[1, [2, [3, [4, 5]]], 6] -> [1, 2, 3, 4, 5, 6]

代码实现

/**
 * @constructor
 * @param {NestedInteger[]} nestedList
 * @return {Integer[]}
 */
let flatten = (nestedList) => {
  let result = [];
  let fn = function (target, ary) {
    for (let i = 0; i < ary.length; i++) {
      let item = ary[i];
      if (Array.isArray(item)) {
        fn(target, item);
      } else {
        target.push(item);
      }
    }
  }
  fn(result, nestedList)
  return result;
}

同时可采用 reduce 的方式, 一行就可以解决，非常简洁。

let flatten = (nestedList) => {
  nestedList.reduce((pre, cur) => pre.concat(Array.isArray(cur) ? flatten(cur): cur), []);
};

---

Last update: May 28, 2021