LeetCode如何判斷回文鏈表

題目描述：

請(qǐng)判斷一個(gè)鏈表是否為回文鏈表。

示例 1:

輸入: 1->2輸出: false

示例 2:

輸入: 1->2->2->1輸出: true

思路分析：

迭代法：

避免使用 O(n)O(n) 額外空間的方法就是改變輸入。

我們可以將鏈表的前（后）半部分反轉(zhuǎn)（修改鏈表結(jié)構(gòu)），然后將前半部分和后半部分進(jìn)行比較。比較完成后我們應(yīng)該將鏈表恢復(fù)原樣。雖然不需要恢復(fù)也能通過(guò)測(cè)試用例，但是使用該函數(shù)的人通常不希望鏈表結(jié)構(gòu)被更改。

該方法雖然可以將空間復(fù)雜度降到 O(1)O(1)，但是在并發(fā)環(huán)境下，該方法也有缺點(diǎn)。在并發(fā)環(huán)境下，函數(shù)運(yùn)行時(shí)需要鎖定其他線程或進(jìn)程對(duì)鏈表的訪問(wèn)，因?yàn)樵诤瘮?shù)執(zhí)行過(guò)程中鏈表會(huì)被修改。

整個(gè)流程可以分為以下步驟：

找到前（后）半部分鏈表的尾節(jié)點(diǎn)。
反轉(zhuǎn)（前）后半部分鏈表。
判斷是否回文。

Python實(shí)現(xiàn)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None or head.next is None:
            return True
        if head.next.next is None:
            return head.val == head.next.val
        fast = slow = q = head
        while fast.next and fast.next.next:#這里快指針的判讀條件跟判斷環(huán)形有一點(diǎn)不同
            fast = fast.next.next
            slow = slow.next
        def reverse_list(head):
            if head is None:
                return head
            cur = head
            pre = None
            nxt = cur.next
            while nxt:
                cur.next = pre
                pre = cur
                cur = nxt
                nxt = nxt.next
            cur.next = pre
            return cur
        p = reverse_list(slow.next)
        while p.next:
            if p.val != q.val:
                return False
            p = p.next
            q = q.next
        return p.val == q.val

java實(shí)現(xiàn)：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        ListNode slow=head;
        ListNode fast=head;
        ListNode pre=null,prepre=null;
       //反轉(zhuǎn)前半部分指針
        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(pre!=null&&slow!=null){
            if(pre.val!=slow.val){
                return false;
            }
            pre=pre.next;
            slow=slow.next;
        }
        return true; 
    }
}

遞歸法：

currentNode 指針是先到尾節(jié)點(diǎn)，由于遞歸的特性再?gòu)暮笸斑M(jìn)行比較。frontPointer 是遞歸函數(shù)外的指針。若 currentNode.val != frontPointer.val 則返回 false。反之，frontPointer 向前移動(dòng)并返回 true。

算法的正確性在于遞歸處理節(jié)點(diǎn)的順序是相反的，而我們?cè)诤瘮?shù)外又記錄了一個(gè)變量，因此從本質(zhì)上，我們同時(shí)在正向和逆向迭代匹配。

所謂遞歸，即從上往下遞下去，然后再?gòu)南峦蠚w回來(lái)。

java實(shí)現(xiàn)代碼：

class Solution {
    private ListNode frontPointer;

    private boolean recursivelyCheck(ListNode currentNode) {
        if (currentNode != null) {
            if (!recursivelyCheck(currentNode.next)) {
                return false;
            }
            if (currentNode.val != frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }

    public boolean isPalindrome(ListNode head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }