Palindrome Linked List

描述

Given a singly linked list, determine if it is a palindrome.

Follow up:

Could you do it in O(n) time and O(1) space?

分析

首先要寻找中点，原理是使用快慢指针，每次快指针走两步，慢指针走一步。同时还要用栈，每次慢指针走一步，都把值存入栈中。等快指针走完时，链表的前半段都存入栈中了。最后慢指针继续往前走，每次与栈顶元素进行比较。空间复杂度O(n)。

如何做到用O(1)空间呢？可以先找到中点，把后半段reverse一下，然后比较两个小链表。

代码

  1. // Palindrome Linked List
  2. // Time Complexity: O(n), Space Complexity: O(1)
  3. public class Solution {
  4.     public boolean isPalindrome(ListNode head) {
  5.         if (head == null) return true;
  7.         final ListNode middle = findMiddle(head);
  8.         middle.next = reverse(middle.next);
  10.         ListNode p1 = head;
  11.         ListNode p2 = middle.next;
  12.         while (p1 != null && p2 != null && p1.val == p2.val) {
  13.             p1 = p1.next;
  14.             p2 = p2.next;
  15.         }
  16.         return p2 == null;
  18.     }
  19.     private static ListNode findMiddle(ListNode head) {
  20.         if (head == null) return null;
  22.         ListNode slow = head;
  23.         ListNode fast = head.next;
  25.         while (fast != null && fast.next != null) {
  26.             slow = slow.next;
  27.             fast = fast.next.next;
  28.         }
  29.         return slow;
  30.     }
  32.     private static ListNode reverse(ListNode head) {
  33.         ListNode prev = null;
  35.         while (head != null) {
  36.             ListNode tmp = head.next;
  37.             head.next = prev;
  38.             prev = head;
  39.             head = tmp;
  40.         }
  42.         return prev;
  43.     }
  44. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/linked-list/palindrome-linked-list.html