如何判断链表是否为回文结构？

前言

本文介绍单链表相关的一道算法题，判断一个单链表是否为回文结构。

正文

题目描述如下：给出一个单链表的头结点head, 请判断该链表是否为回文结构。

回文指的是两遍对称，用字符串举个例子：1234321、12344321、上海自来水来自海上。

以单链表来说，如图，图中的单链表就属于回文结构：

思路分析

这道题的解法有多种，比如直接有哈希表来判断。

哈希表判断

用哈希表来辅助判断十分简单，判断过程如下：

• 遍历单链表，从头结点开始，将每个节点压入栈中
• 每个节点入栈后，再次回到头结点，准备重新遍历
• 从头结点开始，栈中弹出一个元素和遍历的节点对比
• 如果每一个节点都一样说明，该链表是回文结构

双指针判断

如果不借助额外容器的话，我们还可以使用双指针方式，具体步骤如下：

• 找到链表中间位置，如果是奇数个中间位置为中间节点，如果是偶数个，中间位置为中间的上一个节点位置。
• 找到中间位置后，将中间节点的next指针指向空，将后半部分节点进行逆序。
• 分别从头和尾部一个一个遍历判断，看每一个节点的值是否相同

如果是奇数个节点的链表，调整节点后，示例图如下：

如果是偶数个节点的链表，调整节点后，示例图如下：

使用双指针方法来判断，需要实现一个返回中间节点的函数以及一个把链表逆序的函数。

需要注意的是，在判断这个链表是否回文后，要把逆序的部分再给调回去，也就是还原现场~

代码实现

根据上面的分析，来看一下代码实现，把两种方式都实现一下：

哈希表判断

public boolean isPalindrome(Node head) {
   Stack<Node> stack = new Stack<>();
   Node cur = head;
   // 先把所有节点都压栈
   while (cur != null) {
      stack.push(cur);
      cur = cur.next;
   }
   while (head != null) {
      // 从栈中弹出节点对比节点值
      if (head.value != stack.pop().value) {
         return false;
      }
      head = head.next;
   }
   return true;
}

双指针判断

双指针比较考验编码能力，相对于上一种方式来说，复杂一些，代码如下：

public boolean isPalindrome(Node head) {
    if (head == null || head.next == null) {
        return true;
    }
    // 记录中间节点
    Node n1 = head;
    // 记录结尾节点
    Node n2 = head;
    // 查询中间节点
    while (n2.next != null && n2.next.next != null) { 
        n1 = n1.next;
        n2 = n2.next.next;
    }

    // 有半部分的第一个节点
    n2 = n1.next;
    n1.next = null;
    Node n3 = null;
    // 将有半部分链表逆序
    while (n2 != null) {
            n3 = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 = n3;
    }
    n3 = n1;
    n2 = head;
    boolean res = true;
    // 从两端开始对比
    while (n1 != null && n2 != null) {
    // 如果对比过程不相等，不能直接return，先记录下
        if (n1.value != n2.value) {
                res = false;
                break;
        }
        n1 = n1.next;
        n2 = n2.next;
    }
    n1 = n3.next;
    n3.next = null;
    // 还原右半部分，还原现场
    while (n1 != null) {
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
    }
    return res;
}

总结

本文介绍如何判断一个单链表是否为回文结构，实现这个功能有多种做法，本次介绍了哈希表和快慢指针两种方式。

如果是在机试的时候遇到，直接使用哈希表就行，能计算出结果就好，至于如何实现一般不会关注。如果是面试过程问的话，那就用快慢指针的方式，这样显得比较有技术含量。

今天的分享就到这里了，如果对你有帮助的话，就辛苦帮忙点个赞吧，生着病码字也不容易，呜呜┭┮﹏┭┮