面试算法27：回文链表

回文链表"/>

面试算法27：回文链表

问题

如何判断一个链表是不是回文？要求解法的时间复杂度是O（n），并且不得使用超过O（1）的辅助空间。如果一个链表是回文，那么链表的节点序列从前往后看和从后往前看是相同的。

分析

如果不考虑辅助空间的限制，直观的解法是创建一个新的链表，链表中节点的顺序和输入链表的节点顺序正好相反。如果新的链表和输入链表是相同的，那么输入链表就是一个回文链表。只是这种解法需要创建一个和输入链表长度相等的链表，因此需要O（n）的辅助空间。

仔细分析回文链表的特点以便找出更好的解法。回文链表的一个特性是对称性，也就是说，如果把链表分为前后两半，那么前半段链表反转之后与后半段链表是相同的。在如图4.13所示的包含6个节点的链表中，前半段链表的3个节点反转之后分别是3、2、1，后半段链表的3个节点也分别是3、2、1，因此它是一个回文链表。

链表的节点总数是偶数。如果链表的节点总数是奇数，那么把链表分成前后两半时不用包括中间节点。例如，一个链表中的节点顺序是1、2、k、2、1，前面两个节点反转之后是2、1，后面两个节点也是2、1，不管中间节点的值是什么该链表都是回文链表。

解

public class Test {public static void main(String[] args) {ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode3 = new ListNode(3);ListNode listNode11 = new ListNode(1);ListNode listNode22 = new ListNode(2);ListNode listNode33 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode5 = new ListNode(5);ListNode listNode6 = new ListNode(6);ListNode listNode7 = new ListNode(7);ListNode listNode8 = new ListNode(8);ListNode listNode9 = new ListNode(9);listNode1.next = listNode2;listNode2.next = listNode3;listNode3.next = listNode33;listNode33.next = listNode22;listNode22.next = listNode11;boolean result = isPalindrome(listNode1);System.out.println(result);}public static boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}ListNode slow = head;ListNode fast = head.next;// slow和fast按照两个两个的遍历下去，如果最后fast.next==null，则说明总个数是奇数while (fast.next != null && fast.next.next != null) {fast = fast.next.next;slow = slow.next;}ListNode secondHalf = slow.next;if (fast.next != null) {secondHalf = slow.next.next;}slow.next = null;return equals(secondHalf, reverseList(head));}private static boolean equals(ListNode head1, ListNode head2) {while (head1 != null && head2 != null) {if (head1.val != head2.val) {return false;}head1 = head1.next;head2 = head2.next;}return head1 == null && head2 == null;}public static ListNode reverseList(ListNode head) {ListNode prev = null;ListNode cur = head;while (cur != null) {ListNode next = cur.next;cur.next = prev;prev = cur;cur = next;}return prev;}
}