【算法】判断一个链表是否为回文结构---MapleYe

题目

给定一个链表的头节点head，请判断该链表是否为回 文结构。 例如: 1->2->1，返回true。 1->2->2->1，返回true。 15->6->15，返回true。 1->2->3，返回false。 进阶： 如果链表长度为N，时间复杂度达到O(N)，额外空间复杂 度达到O(1)。

链表结构如下 public static class Node { public Node next; public int value; public Node(int data) { value = data; } }1、基础版--空间复杂度O(N)思路：

使用栈，将链表的所有数据入栈。然后链表从头开始遍历，每次指针指向下一个节点时，栈弹出，判断两者是否相等，直至栈空都相等的话，那么就是回文链表。

代码实现public static boolean isPalindromeList1(Node head) { Stack<Node> stack = new Stack<Node>(); Node p = head; while(p != null) { stack.push(p); p = p.next; } while(head != null) { Node node = stack.pop(); if (node.value != head.value) { return false; } head = head.next; } return true; }2、进阶版1--空间复杂度O(N/2)思路

回顾上面的解法，其实我们只需比较到链表的中点即可。因此，我们不再对链表全部入栈，而是先找到链表的中点，然后从中点开始入栈。最后只需比较链表~中点之间的数据和链表是否一一相等即可

算法实现 public static boolean isPalindromeList2(Node head) { Node right = head.next; Node cur = head.next.next; // 找到中点节点 while(cur.next != null && cur.next.next != null) { right = right.next; cur = cur.next.next; } // 从中间回文开始的节点入栈 Stack<Node> stack = new Stack<Node>(); while(right != null) { System.out.println(right.value); stack.push(right); right = right.next; } // 比较前回文和后回文部分 while(!stack.isEmpty()) { Node node = stack.pop(); if (node.value != head.value) { return false; } head = head.next; } return true; }

这里需要提到中点链表的查找方法： 1、准备一个慢指针，一次走1格 2、准备一个快指针，一次走2格 3、当快指针走完了，那么慢指针所指向的节点就是中点节点。若不理解，自己画图理解理解

3、进阶版2--空间复杂度O(1)思路

修改链表的指向，将回文部分链表逆转指向中点，例如： 1 -> 2 -> 3 -> 2 -> 1改为 1 -> 2 -> 3 <- 2 <- 1 这种结构判断 因此，算法步骤如下： 1、我们需要先找到中点节点，然后修改尾节点~中点节点的指向，翻转节点 2、首尾指针开始遍历链表，直至首尾的指针抵达中点，期间判断首尾指针指向的value是否相等 3、还原链表原来的结构（如果要求不能修改链表结构的话，就需要做这步骤，算是可选步骤吧）

算法实现 public static boolean isPalindromeList3(Node head) { Node right = head.next; Node cur = head.next.next; // 找到中间节点 while(cur.next != null && cur.next.next != null) { right = right.next; cur = cur.next.next; } // 右边第一个节点 Node n1 = right.next; // 使中间节点指向null right.next = null; Node pre = null; Node next = null; // 以中间开始，翻转节点 while(n1 != null) { next = n1.next; n1.next = pre; pre = n1; n1 = next; } // 右边部分的head节点 Node rightHead = pre; Node leftHead = head; // 备份最后的指针 Node lastNode = pre; boolean res = true; while(leftHead != null && rightHead != null) { if(leftHead.value != rightHead.value) { res = false; break; } leftHead = leftHead.next; rightHead = rightHead.next; } // 恢复原来的链表结构，可选步骤 n1 = lastNode; pre = null; next = null; while(n1 != null) { next = n1.next; n1.next = pre; pre = n1; n1 = next; } // 将中间节点重新指向翻转后的最后节点 right.next = pre; return res; } ---来自腾讯云社区的---MapleYe