Leetcode题解之 —— 回文链表

思路

O(n)空间复杂度

  • 数组存储链表的值
  • 转化为回文数解法

O(1)空间复杂度

  • 双字符串保存正反向的val
  • 比对该两者

题解

O(n):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
  const cache = [];
  let current = head;

  while (current) {
    cache.push(current.val);
    current = current.next;
  }

  if (cache.length === 1) {
    return true;
  }

  return cache.join('') === cache.reverse().join('');
};

O(1):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
  let [forwardStr, reverseStr, current] = ['', '', head];

  while (current) {
    forwardStr += current.val;
    reverseStr = '' + current.val + reverseStr;
    current = current.next;
  }

  return forwardStr === reverseStr;
};