LeetCode No.234 回文链表

发表于2020-04-14|更新于2025-01-19|算法

|浏览量:

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

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

转化成数组后使用双指针

首先想到的方法是遍历链表，将链表中的元素添加进数组，然后使用双指针解法，一个指针从前向后扫描，另一个指针从后向前扫描，一旦发现两个指针所指向的元素不同则不是回文，否则两个指针向中间靠拢，如果两个指针相遇，则是回文。这种思路其实是判断回文字符串。

var isPalindrome = function (head) {
  let arr = [];
  let cur = head;
  while (cur) {
    arr.push(cur.val);
    cur = cur.next;
  }
  let i = 0, j = arr.length - 1;
  while (i < j) {
    if (arr[i] !== arr[j]) {
      return false;
    }
    i++;
    j--;
  }
  return true;
}

递归

请看下面的代码：

function print(node) {
  if (!node) return;
  print(node.next);
  console.log(node.val);
}

l = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 3,
      next: {
        val: 4
      }
    }
  }
};

print(l);

上面的算法其实是深度优先遍历，在二分搜索树中遍历中相当于后续遍历的过程，它总是先递归到最深处（这里就是链表的尾节点），然后一层一层返回，因此输出顺序为4-3-2-1。和原来链表的顺序相反。自然而然可以想到：如果维护一个从前向后的指针，到递归到最深处的时候，最深处的节点和第一个节点比较；倒数第二层的节点和第二个节点比较也可以完成回文的判断。代码如下：

var isPalindrome = function (head) {
    let frontPointer = head;

    function recursiveCheck(curNode) {
        if (curNode) {
	    // 这个检测放在第一行保证递归到最深处  	
            if (!recursiveCheck(curNode.next)) return false;
            if (curNode.val !== frontPointer.val) return false;
            frontPointer = frontPointer.next;
        }
        return true;
    }

    return recursiveCheck(head);
};

之所以起作用的原因是递归处理节点的顺序是相反的（记住上面打印的算法）。由于递归，从本质上，我们同时在正向和逆向迭代。

这种方法看似非常惊艳，其实受限于栈空间的大小，限制了能处理的链表的大小。

反转后半部分链表

先反转后半部分链表，然后将前半部分和后半部分进行比较，比较完成后复原链表（为了不改变链表）.

我们可以分为以下几个步骤：

找到前半部分链表的尾节点。
反转后半部分链表。
判断是否为回文。
恢复链表。
返回结果。

执行步骤一，我们可以计算链表节点的数量，然后遍历链表找到前半部分的尾节点。或者可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针到链表的中间。通过慢指针将链表分为两部分。若链表有奇数个节点，则中间的节点应该看作是前半部分。

步骤二可以使用在反向链表问题中找到解决方法来反转链表的后半部分。

步骤三比较两个部分的值，当后半部分到达末尾则比较完成，可以忽略计数情况中的中间节点。

步骤四与步骤二使用的函数相同，再反转一次恢复链表本身。

var isPalindrome = function (head) {

    // 反转后半部分链表
    if (!head) return true;

    const firstHalfEnd = endOfFirstHalf(head);
    const secondHalfStart = reverseList(firstHalfEnd.next);

    let p1 = head;
    let p2 = secondHalfStart;

    let result = true;
    while (p2) {
        if (p1.val !== p2.val) {
            result = false;
            break;
        }
        p1 = p1.next;
        p2 = p2.next;
    }

    firstHalfEnd.next = reverseList(secondHalfStart);
    return result;

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

    function endOfFirstHalf(head) {
        let fast = head,
            slow = head;
        while (fast.next && fast.next.next) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
};