#234. Palindrome Linked List

題目描述

給你一個鏈結串列的起點head，如果是一個回文鏈結串列回傳true，不是則回傳false。

限制條件

節點數量為[1, 10^5]。
0 <= 節點值 <= 9

解題思路

Hash Table

由於我們只知道鏈結串列的起點，要知道所有的節點順序勢必要走完所有的節點，但因為無法直接指定某個位置的節點，所以要想辦法解決這個問題，這個時候就可以借助HashTable來記憶所有的節點順序，知道順序以後在前後比對就可以了。

public class Solution { 
	public bool IsPalindrome(ListNode head) {
        if(head.next==null) return true;
        var ht = new Hashtable();
        int count = 0;
        while(head!=null){
            ht.Add(count,head.val);
            head = head.next;
            count++;
        }
        int half = count/2;
        count--;
        for(int i=0;i<half;i++){
            if((int)ht[i]!=(int)ht[count]) return false;
            count--;
        }   
        return true;
    }
}

複雜度分析：

時間複雜度：紀錄節點的順序時間為n，比對節點的時間為n/2，總花費時間為3/2n，因此時間複雜度為O(n)。
空間複雜度：要儲存節點順序，因此空間複雜度為O(n)。

Follow-up

你可以讓執行時間為O(n)以及使用O(1)的空間嗎？

Divide and Reverse

若要讓空間複雜度為O(1)，就不能使用Hash Table來解決這一題，所以我們要換個方式。
首先先確定整個鏈結串列的長度，得到中間值，接著從中間的節點開始把鏈結反向，然後就會得到從尾端開始的鏈結串列，只要比對從頭開始和從尾端開始的值，就可以知道鏈結串列是否為回文結構了。

public class Solution { 
	public bool IsPalindrome(ListNode head) {        
        if(head==null ||head.next==null) return true;
        var temp = head;
        var count = 0;
        while(temp!=null){
            temp = temp.next;
            count++;
        }
        temp = head;
        count/=2;
        for(int i=0;i<count;i++){
            temp = temp.next;
        }                
        var tail = Reverse(temp);        
        if(tail==null) return false;
        while(head!=null && tail!=null){            
            if(head.val != tail.val) return false;
            head = head.next;
            tail = tail.next;
        }
        return true;
    }
    public ListNode Reverse(ListNode head){
        if(head==null ||head.next==null) return head;
        var prev = head;
        var curr = head.next;
        head.next = null;
        while(curr.next!=null){
            var next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        curr.next = prev;
        return curr;
    }
}

複雜度分析：

時間複雜度：找出長度的時間為n，定位中間節點的時間為n/2，反轉節點為n/2，比對節點為n/2，總時間為5/2n，因此時間複雜度為O(n)。
空間複雜度：空間複雜度為O(1)。

Two Pointers

雖然上面的解法可以解決掉問題，但是步驟太繁瑣了，可以做出一些調整來改善。首先可以改成利用雙指標法，快指標的速度是慢指標的兩倍，所以當快指標到達終點時，慢指標剛好走到中間。然而這邊仍然要把節點反向才能夠去比對節點，但是可以不用等到找到中間點才開始做，只要慢指標開始移動時，邊移動邊把當下的節點做反向即可。並且當慢指標走道中間時，就可以馬上進行比對了。

public class Solution { 
	public bool IsPalindrome(ListNode head) {
        if(head==null || head.next==null) return true;
        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;        
        while(fast!=null && fast.next!=null){            
            fast = fast.next.next;
            ListNode tmp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = tmp;
        }        
        if(fast!=null) slow = slow.next;
        while(slow!=null){
            if(slow.val!=prev.val) return false;
            slow = slow.next;
            prev = prev.next;
        }
        return true;
    }
}

複雜度分析：

時間複雜度：快慢指標找到中間節點位置時，只花了n/2的時間，而從中間開始比對也只花了n/2的時間，所以總共花費了n的時間，因此時間複雜度為O(n)。
空間複雜度：空間複雜度為O(1)。

學習重點

雜湊表(Hash Table)。
雙指標(Two Pointers)。