一道新的面試題回文鏈表你會么？

作者：程序員Carl 2021-10-28 11:40:58

在我們的生活中經(jīng)常會碰到這種回文的結(jié)構(gòu)，回文就是反轉(zhuǎn)以后和以前一樣的就是回文結(jié)構(gòu)，例如 1->2->3->2->1，我們將它反轉(zhuǎn)之后還是與原鏈表一樣，我們就稱這種鏈表結(jié)構(gòu)為回文結(jié)構(gòu)。

[[431751]]

新題來咯，回文鏈表

回文鏈表

力扣題目鏈接：https://leetcode-cn.com/problems/palindrome-linked-list/

請判斷一個鏈表是否為回文鏈表。

示例 1:

輸入: 1->2
輸出: false

示例 2:

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

思路

數(shù)組模擬

最直接的想法，就是把鏈表裝成數(shù)組，然后再判斷是否回文。

代碼也比較簡單。如下：

class Solution { 
public: 
    bool isPalindrome(ListNode* head) { 
        vector<int> vec; 
        ListNode* cur  = head; 
        while (cur) { 
            vec.push_back(cur->val); 
            cur = cur->next; 
        } 
        // 比較數(shù)組回文 
        for (int i = 0, j = vec.size() - 1; i < j; i++, j--) { 
            if (vec[i] != vec[j]) return false; 
        } 
        return true; 
    } 
};

上面代碼可以在優(yōu)化，就是先求出鏈表長度，然后給定vector的初始長度，這樣避免vector每次添加節(jié)點(diǎn)重新開辟空間

class Solution { 
public: 
    bool isPalindrome(ListNode* head) { 
 
        ListNode* cur  = head; 
        int length = 0; 
        while (cur) { 
            length++; 
            cur = cur->next; 
        } 
        vector<int> vec(length, 0); // 給定vector的初始長度，這樣避免vector每次添加節(jié)點(diǎn)重新開辟空間 
        cur = head; 
        int index = 0; 
        while (cur) { 
            vec[index++] = cur->val; 
            cur = cur->next; 
        } 
        // 比較數(shù)組回文 
        for (int i = 0, j = vec.size() - 1; i < j; i++, j--) { 
            if (vec[i] != vec[j]) return false; 
        } 
        return true; 
    } 
};

反轉(zhuǎn)后半部分鏈表

分為如下幾步：

用快慢指針，快指針有兩步，慢指針走一步，快指針遇到終止位置時，慢指針就在鏈表中間位置
同時用pre記錄慢指針指向節(jié)點(diǎn)的前一個節(jié)點(diǎn)，用來分割鏈表
將鏈表分為前后均等兩部分，如果鏈表長度是奇數(shù)，那么后半部分多一個節(jié)點(diǎn)
將后半部分反轉(zhuǎn) ，得cur2，前半部分為cur1
按照cur1的長度，一次比較cur1和cur2的節(jié)點(diǎn)數(shù)值

如圖所示：

代碼如下：

class Solution { 
public: 
    bool isPalindrome(ListNode* head) { 
        if (head == nullptr || head->next == nullptr) return true; 
        ListNode* slow = head; // 慢指針，找到鏈表中間分位置，作為分割 
        ListNode* fast = head; 
        ListNode* pre = head; // 記錄慢指針的前一個節(jié)點(diǎn)，用來分割鏈表 
        while (fast && fast->next) { 
            pre = slow; 
            slow = slow->next; 
            fast = fast->next->next; 
        } 
        pre->next = nullptr; // 分割鏈表 
 
        ListNode* cur1 = head;  // 前半部分 
        ListNode* cur2 = reverseList(slow); // 反轉(zhuǎn)后半部分，總鏈表長度如果是奇數(shù)，cur2比cur1多一個節(jié)點(diǎn) 
 
        // 開始兩個鏈表的比較 
        while (cur1) { 
            if (cur1->val != cur2->val) return false; 
            cur1 = cur1->next; 
            cur2 = cur2->next; 
        } 
        return true; 
    } 
    // 反轉(zhuǎn)鏈表 
    ListNode* reverseList(ListNode* head) { 
        ListNode* temp; // 保存cur的下一個節(jié)點(diǎn) 
        ListNode* cur = head; 
        ListNode* pre = nullptr; 
        while(cur) { 
            temp = cur->next;  // 保存一下 cur的下一個節(jié)點(diǎn)，因?yàn)榻酉聛硪淖僣ur->next 
            cur->next = pre; // 翻轉(zhuǎn)操作 
            // 更新pre 和 cur指針 
            pre = cur; 
            cur = temp; 
        } 
        return pre; 
    } 
};

其他語言版本

Java

// 方法一，使用數(shù)組 
class Solution { 
    public boolean isPalindrome(ListNode head) { 
        int len = 0; 
        // 統(tǒng)計鏈表長度 
        ListNode cur = head; 
        while (cur != null) { 
            len++; 
            cur = cur.next; 
        } 
        cur = head; 
        int[] res = new int[len]; 
        // 將元素加到數(shù)組之中 
        for (int i = 0; i < res.length; i++){ 
            res[i] = cur.val; 
            cur = cur.next; 
        } 
        // 比較回文 
        for (int i = 0, j = len - 1; i < j; i++, j--){ 
            if (res[i] != res[j]){ 
                return false; 
            } 
        } 
        return true; 
    } 
} 
 
// 方法二，快慢指針 
class Solution { 
    public boolean isPalindrome(ListNode head) { 
        // 如果為空或者僅有一個節(jié)點(diǎn)，返回true 
        if (head == null && head.next == null) return true; 
        ListNode slow = head; 
        ListNode fast = head; 
        ListNode pre = head; 
        while (fast != null && fast.next != null){ 
            pre = slow;  // 記錄slow的前一個結(jié)點(diǎn) 
            slow = slow.next; 
            fast = fast.next.next; 
        } 
        pre.next = null;  // 分割兩個鏈表 
 
        // 前半部分 
        ListNode cur1 = head; 
        // 后半部分。這里使用了反轉(zhuǎn)鏈表 
        ListNode cur2 = reverseList(slow); 
 
        while (cur1 != null){ 
            if (cur1.val != cur2.val) return false; 
 
            // 注意要移動兩個結(jié)點(diǎn) 
            cur1 = cur1.next; 
            cur2 = cur2.next; 
        } 
        return true; 
    } 
    ListNode reverseList(ListNode head){ 
        // 反轉(zhuǎn)鏈表 
        ListNode tmp = null; 
        ListNode pre = null; 
        while (head != null){ 
            tmp = head.next; 
            head.next = pre; 
            pre = head; 
            head = tmp; 
        } 
        return pre; 
    } 
}

Python

#數(shù)組模擬 
class Solution: 
    def isPalindrome(self, head: ListNode) -> bool: 
        length = 0 
        tmp = head 
        while tmp: #求鏈表長度 
            length += 1 
            tmp = tmp.next 
 
        result = [0] * length 
        tmp = head 
        index = 0 
        while tmp: #鏈表元素加入數(shù)組 
            result[index] = tmp.val 
            index += 1 
            tmp = tmp.next 
 
        i, j = 0, length - 1 
        while i < j: # 判斷回文 
            if result[i] != result[j]: 
                return False 
            i += 1 
            j -= 1 
        return True 
 
#反轉(zhuǎn)后半部分鏈表 
class Solution: 
    def isPalindrome(self, head: ListNode) -> bool: 
        if head == None or head.next == None: 
            return True 
        slow, fast = head, head 
        while fast and fast.next: 
            pre = slow 
            slow = slow.next 
            fast = fast.next.next 
 
        pre.next = None # 分割鏈表 
        cur1 = head # 前半部分 
        cur2 = self.reverseList(slow) # 反轉(zhuǎn)后半部分，總鏈表長度如果是奇數(shù)，cur2比cur1多一個節(jié)點(diǎn) 
        while cur1: 
            if cur1.val != cur2.val: 
                return False 
            cur1 = cur1.next 
            cur2 = cur2.next 
        return True 
 
    def reverseList(self, head: ListNode) -> ListNode: 
        cur = head 
        pre = None 
        while(cur!=None): 
            temp = cur.next # 保存一下cur的下一個節(jié)點(diǎn) 
            cur.next = pre # 反轉(zhuǎn) 
            pre = cur 
            cur = temp 
        return pre