234 Palindrome Linked List

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

Example：

Input: 1->2
Output: false

Input: 1->2->2->1
Output: true

Note：

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

解释下题目：

判断一个链表是不是回文链表

1. 利用数据结构进行存储

实际耗时：3ms

public boolean isPalindrome(ListNode head) {
    LinkedList<Integer> deque = new LinkedList<>();
    ListNode fakeHead = head;
    while (head != null) {
        deque.addLast(head.val);
        head = head.next;
    }
    while (!deque.isEmpty()) {
        if (deque.size() == 1) {
            return true;
        }
        int start = deque.getFirst();
        int end = deque.getLast();
        deque.removeFirst();
        deque.removeLast();
        if (start != end) {
            return false;
        }
    }
    return true;
}

  思路很简单，用Linkedlist进行存储，然后进行比较。优点是很简单，易于理解，缺点就是比较费空间。如果希望能够节省空间，可以用两个指针，一个指针一次走一步，另外一个指针一次走两步，然后这样就能走到中间。最后通过链表的逆转就能判断。

时间复杂度O(n)

空间复杂度O(n)