Question:

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?

Analysis:

给出一个链表，能否在O(n)的时间和O(1)的空间内判断链表是否为回文链表。

由于题目给出了严格的时间和空间复杂度的要求，

1）首先，遍历一遍链表，将数字放在一个数组里，然后比较数组中的数据，这样空间复杂度为O(n)，不符合要求；

2）（看到网络大神们的思路利用栈）这种方法是我从来没有去思考过的思路，虽然无法解决这个问题，但是是一种很好的解决问题的方法。利用栈先进后出的特点，将前半部分放入栈中，然后与后半部分做比较。空间复杂度为O(n/2)，思路很棒~

3）不使用额外空间，首先使用快慢指针法找到链表的中间，然后将后半部分就地转置，最后遍历一半的链表进行比较即可。

Answer：

public boolean isPalindrome(ListNode head) {        if(head == null || head.next == null)            return true;        //使用快慢指针法找到链表的中间,最终slow指向的就是链表的中间        ListNode fast = head, slow = head;        while(fast != null && fast.next != null) {            fast = fast.next.next;            slow = slow.next;        }                //将链表的后半段就地转置        if(fast == null) { //如果有偶数个节点            slow = reverseList(slow);        } else { //有奇数个节点            slow.next = reverseList(slow.next);            slow = slow.next;        }                //比较链表的前半段，与转置后的后半段是否一致        fast = head;        while(fast.next != null && slow.next != null) {            if(fast.val != slow.val)                return false;            fast = fast.next;            slow = slow.next;        }                return true;    }        public ListNode reverseList(ListNode head) {        if(head == null || head.next == null)            return head;        ListNode h = head;        while(head.next != null) {            ListNode p = head.next;            head.next = p.next;            p.next = h;            h = p;        }        return h;    }

 相关题目：