[LeetCode刷題筆記] 234 – Palindrome Linked List

題目描述：

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

Example 1:

Input: 1->2
Output: false

Example 2:

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

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

一刷題解（快慢指針）：

這題要我們檢查一個鏈表的值在順序輸出後的結果是否一個互文。我們可以通過快慢指針以及逆轉鏈表指向的思路來完成。首先我們創造兩個指針，一個指針的前移速度是另外一個個指針的兩倍，這樣一來，當快指針對達鏈表的終點時，慢指針就正處於鏈表的中間。

然後我們先將快指針還原到起點，再利用慢指針，一步一步將鏈表後半段的指向逆轉（從與前半段一樣指向後面逆轉為指向前半段），當慢指針到達鏈表的盡頭（舊鏈表的結尾，新鏈表的起點）後，形成一個「首末端指向中間」的鏈表結構，並擁有兩個分別位於鏈表兩端的指針，最後只要使這兩個指針均速前進即可。如果前進到各自的盡頭也沒有發現差異，代表這是一個「互文的鏈表」。

public class Solution {
    public bool IsPalindrome(ListNode head) {                               
        ListNode fast = head;
        ListNode slow = head;
        
        while(fast != null && fast.next != null)
        {
            fast = fast.next.next;
            slow = slow.next;
        }
        
        fast = head;
        slow = Reverse(slow); //反轉後半段的指向
        
        //首端與末端同時向前移動
        while(slow != null && fast != null)
        {
            if(fast.val != slow.val) { return false; }
            fast = fast.next;
            slow = slow.next;                        
        }
        
        return true;
    }
    
    ListNode Reverse(ListNode node)
    {
        ListNode prev = null;
        ListNode curr = node;
        
        while(curr != null)
        {
            ListNode originNext = curr.next;
            curr.next = prev;
            prev = curr;
            curr = originNext;            
        }
        
        return prev;
    }
}