leetcode234~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?

思路： 判斷一個連結清單是否是回文連結清單，幾種解法都會使用到倆指針，用來從中間分割連結清單。

1 将前部分的連結清單元素放入數組中，然後在周遊後半部分的連結清單時，和資料中逆序元素進行比較

2 将前部分的連結清單元素放在list集合中，使用add(0,value)方法，每次都是從頭插入，然後比較

3 利用堆棧的先進後出特性

4 将後半部分連結清單原地翻轉

隻有第四種的空間複雜度是O(1)

public class PalindromeLinkedList {
    public boolean isPalindrome(ListNode head) {
        if(head==null) return true;
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null && fast.next.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode rhead = slow.next;
        slow.next = null;
        //對後半部分連結清單翻轉
        ListNode pre = null;
        while(rhead!=null) {
            ListNode tmp = rhead.next;
            rhead.next = pre;
            pre = rhead;
            rhead = tmp;
        }
        //此時pre是翻轉後的頭節點
        while(head!=null && pre!=null) {
            if(head.val!=pre.val) {
                return false;
            }
            head = head.next;
            pre = pre.next;
        }
        return true;
    }

    //使用堆棧實作
    public boolean isPalindrome2(ListNode head) {
        if(head==null) return true;
        Stack<Integer> stack = new Stack<Integer>();
        ListNode slow=head,fast=head;
        //将第一個元素進棧
        stack.push(slow.val);
        while(fast.next!=null && fast.next.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
            //入棧
            stack.push(slow.val);
        }

        //這裡需要對連結清單長度進行判斷 如果為奇數，則中間那個節點值也進棧了 如果為偶數，則比較應該從下一個節點開始
        if(fast!=null) {
            slow = slow.next;
        }
        while(slow!=null) {
            if(slow.val!=stack.pop()) {
                return false;
            }
            slow = slow.next;
        }
        return true;
    }
}