LeetCode234回文連結清單(快慢指針)

題目

不進階的話這裡我用的是棧解決的 前半段入棧 然後邊出棧邊和後半段比較 代碼比較好些就不貼上來了

進階方法是快慢指針 快指針指向結尾時 慢指針指向中間 過程中反轉從頭到中間結點這段連結清單 然後正向的和慢指針接下來指向的後半段連結清單逐個比較

注意一下如果連結清單長度為奇數 慢指針需要先向後移動一位再比較 将中間數跳過

public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode slow = head ,fast = head;
        ListNode pre = head , prepre = null;//構造一個反轉連結清單
        while (fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
            pre.next = prepre;//目前結點指向上一次周遊的結點
            prepre = pre;
        }
        if (fast != null) slow = slow.next;//如果長度為奇數 需要将中位數跳過在比較
        while (slow != null){
            if (slow.val != pre.val) return false;
            slow = slow.next;
            pre = pre.next;
        }
        return true;
    }