題目

• 給定一個鏈表，判定它是否是回文鏈表
• 舉例：1->2返回false 1->2->2->1返回true
• 時間復雜度O(n)空間復雜度O(1)

解析方法

• 如果沒有時間復雜度為O(n)，空間復雜度O(1)的要求，那么這個解題方法很多，可以新建一個鏈表然后逆序比較兩個鏈表是否相等即可得到結果，這樣做時間復雜度O(n)空間復雜度O(n)
• 采用二分的方法，先找到中間節(jié)點截斷然后將后半部分逆序，前半部分和后半部分對比，如果完全相同那么后半部分遍歷后的指向是null此時表示這個鏈表是回文，如果后半部分指針不是null那么表示循環(huán)提前結束了也就不是回文鏈表。

源代碼實現

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) slow = slow.next;//奇數需要走到下一個才是后半部分的開頭
        slow = reverse(slow);//將后半段列表反轉
        while (slow != null && slow.val == head.val) {
            slow = slow.next;
            head = head.next;
        }
        return slow == null;
    }
    
    //反轉方法1頭插法，開銷比較大
    private ListNode reverse(ListNode head) {
        ListNode front = new ListNode(0);
        while (head != null) {
            ListNode temp = head;
            head = head.next;
            temp.next = front.next;
            front.next = temp;
        }
        return front.next;
    }
    //反轉方法二
    private ListNode reverse1(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

代碼分析

• 首先尋找中間節(jié)點所需時間是n/2,反轉所需時間也是n/2，其次比較的時間也是需要n/2，所以整體時間是3n/2,所以時間復雜度是O(n),空間復雜度常數O(1)