链表在数据结构与算法中可谓“北斗之尊”，现在让我们通过判断链表回文的小练习进一步更深地了解链表~

文章目录

一、链表的节点结构二、判断一个链表是否为回文结构（一）解法1：将链表全部节点进栈出栈比较（空间复杂度为O(N)）（二）解法2：将链表右半部分节点进栈出栈比较（空间复杂度为O(2/N)）（三）解法3：快慢指针+指针逆序解法（空间复杂度为O(1)，符合题目要求）

简单回顾一下链表的结构~

一、链表的节点结构

1.单链表的节点结构

Class Node<V>{V value;Node next;}

由以上结构的节点依次连接起来所形成的链叫单链表结构

2.双链表的节点结构

Class Node<V>{V value;Node next;Node last;}

由以上结构的节点依次连接起来所形成的链叫双链表结构

单链表和双链表结构只需要给定一个头部节点head，就可以找到剩下的所有的节点

二、判断一个链表是否为回文结构

【题目】给定一个单链表的头节点head，请判断该链表是否为回文结构。

【例子】1->2->3，返回true；1->2->2->1，返回true；1->2->3，返回false。

【要求】如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。

思想：

假设有这么一组数，需要判断它是否是回文

（一）解法1：将链表全部节点进栈出栈比较（空间复杂度为O(N)）

解题思路：

1、先将原链表依次进栈（先进后出）

2、再将栈中元素依次出栈

3、每次出栈都与原链表从头节点开始比较，如果比较完都一致，说明是回文链表

代码如下：

/** 第一种思路：需要n个额外空间，将全部节点入栈，再依次出栈与原来节点顺序比较，* 看是否是回文* */public static boolean isPalindrome1(Node head) {Stack<Node> stack = new Stack<Node>();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;}

（二）解法2：将链表右半部分节点进栈出栈比较（空间复杂度为O(2/N)）

解题思路：（对称思想）

1、先用快慢指针法找到链表中间节点位置

快慢指针概念：

快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。

2、将中间节点以后的部分放进栈中（右半部分）

3、右半部分出栈，与原链表左半部分依次进行比较，直到栈为空

4、如果比较结果一致，说明是回文链表

代码如下：

/** 第二种思路：需要n/2个额外空间，用快慢指针找到中间节点，将中间节点以后的节点放入栈中，* 再出栈同时与原来中间节点以前的另一半部分比较，相同则是回文* */public static boolean isPalindrome2(Node head) {if (head == null || head.next == null) {return true;}Node right = head.next; //right指针最后指向中点右边第一个节点Node cur = head;while (cur.next != null && cur.next.next != null) {right = right.next;cur = cur.next.next;}Stack<Node> stack = new Stack<Node>();while (right != null) {//将右半部分放入栈中stack.push(right);right = right.next;}while (!stack.isEmpty()) {//栈不为空时if (head.value != stack.pop().value) {//栈中弹出来的节点和原链表从头节点开始对比，直到栈弹空return false;}head = head.next;}return true;}

（三）解法3：快慢指针+指针逆序解法（空间复杂度为O(1)，符合题目要求）

解题思路：

1、先用快慢指针找到中点位置，我们想让快指针一次走两步，慢指针一次走一步，这样当快指针结束的时候，慢指针刚好来到了中点的位置。

2、将慢指针指向的节点去指向null，再将后面右半部分的指针逆序（为了后面首尾两头往中间靠拢的时候进行比较）

3、链表头尾各用一个引用去记，然后同时往中间遍历，每次走一步，用两边引用指向的进行比较，直到一边为null，则停止，如果比较结果都为true，则说明是回文。注意最后返回结果前将逆序指针恢复原状。

完整代码如下，包含测试用例：

public class IsPalindromeList {public static void main(String[] args) {Node head = new Node(1);Node n1 = new Node(2);Node n2 = new Node(3);Node n3 = new Node(2);Node n4 = new Node(1);head.next = n1;n1.next = n2;n2.next = n3;n3.next = n4;n4.next = null;//System.out.println(isPalindrome1(head)); //方法1//System.out.println(isPalindrome2(head)); //方法2System.out.println(isPalindrome3(head)); //方法3}public static class Node {public int value;public Node next;public Node(int data) {this.value = data;}}/** 第三种思路：需要O(1)个额外空间，思路见最上方（推荐使用）* 解题思路：* 1、先用快慢指针找到中点位置，我们想让快指针一次走两步，慢指针一次走一步，这样当快指针结束的时候，慢指针刚好来到了中点的位置。* 2、将慢指针指向的节点去指向null，从中点处往下遍历的时候将后面的指针逆序* 3、链表头尾各用一个引用去记，然后同时往中间遍历，每次走一步，直到一边为null，则停止，期间两边引用指向的值相同，则说明是回文。最后返回结果前将逆序指针恢复原状。* */public static boolean isPalindrome3(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; //n1最终走到中点位置n2 = n2.next.next; //n2最终走到结尾}n2 = n1.next; //n2指向n1下一个节点，也就是开始逆序n1.next = null; //将慢指针的下个节点指向nullNode n3 = null;while (n2 != null) {//右半部分都进行逆序n3 = n2.next; //n3用来保存下一个节点n2.next = n1;n1 = n2;n2 = n3;}n3 = n1; //n3 --> 保存最后一个节点n2 = head; //n2 --> 左边第一个节点boolean res = true;while (n1 != null && n2 != null) {//检查回文if (n1.value != n2.value) {res = false; //结果不一样就是false，否则为truebreak;}n1 = n1.next; //n1从左边往中间走n2 = n2.next; //n2从右边往中间走}n1 = n3.next;n3.next = null;while (n1 != null) {//将逆序复原n2 = n1.next;n1.next = n3;n3 = n1;n1 = n2;}return res;}}

第三种方法可以好好钻研一下，面试官看了直呼内行！！！！