精選力扣500題 第40題 LeetCode 234. 回文連結清單【c++/java詳細題解】

目錄

• ​​1、題目​​
• ​​2、思路​​
• ​​3、c++代碼​​
• ​​4、java代碼​​

1、題目

請判斷一個連結清單是否為回文連結清單。

示例 1:

輸入: 1->2
輸出: false      

示例 2:

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

進階：

你能否用 時間複雜度和 空間複雜度解決此題？

2、思路

(連結清單操作)

假設初始的連結清單是 。

分兩步處理：

• 找到連結清單的中點節點，将其後半段的指針都反向，變成：;

  

• 然後用兩個指針分别從連結清單首尾開始往中間掃描，依次判斷對應節點的值是否相等，如果都相等，說明是回文連結清單，否則不是。

  

• 最後再将整個連結清單複原。

注意點：

• 1、我們選取連結清單的中點節點為 下取整，是連結清單的節點個數。
• 2、如果一個連結清單是奇數個節點(假設為5個節點)，将其後半段翻轉完後的連結清單為：

• 3、如果一個連結清單是偶數個節點(假設為4個節點)，将其後半段翻轉完後的連結清單為：

• 4、上圖說明連接配接左右連結清單節點之間的指向是雙向的，具體實作細節看代碼

空間複雜度分析： 連結清單的疊代翻轉算法僅使用額外 的空間，是以本題也僅使用額外 的空間。

3、c++代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int n = 0 ; //統計節點的個數
        for(ListNode *p = head ; p ; p = p->next) n++;
        if(n <= 1) return true; //節點數<=1的一定是回文連結清單
        //找到中點節點，由第一個節點跳(n+1)/2 -1步到達中點節點
        ListNode* a = head;
        for(int i = 0; i < (n+1)/2 - 1; i++) a = a->next; //a指針指向連結清單中點
        ListNode* b = a->next;  //b指針指向連結清單中點的下一個節點
        while(b) //将連結清單的後半段反向
        {
            ListNode* next = b->next; //保留b的next節點
            b->next = a;
            a = b, b = next;
        }
        //此時a指向連結清單的尾節點,我們讓b指向連結清單的頭節點
        b = head;
        ListNode* tail = a; //保留一下尾節點
        bool res = true;
        for(int i = 0; i < n/2; i++) //判斷是否是回文連結清單
        {
            if(b->val  != a->val)
            {
                res = false;
                break;
            }
            b = b->next;
            a = a->next;
        }
        //将連結清單複原，後半段連結清單翻轉
        //a指向尾節點，b指向a的下一個節點
        a = tail, b = a->next;
        for(int i = 0; i < n/2; i++)
        {
            ListNode* next = b->next;
            b->next = a;
            a = b , b = next;
        }
        tail->next = 0;
        return res;
    }
};      

4、java代碼

/**
 * 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) {
        int n = 0 ; //統計節點的個數
        for(ListNode p = head ; p!=null ; p = p.next) n++;
        if(n <= 1) return true; //節點數<=1的一定是回文連結清單
        //找到中點節點，由第一個節點跳(n+1)/2 -1步到達中點節點
        ListNode a = head;
        for(int i = 0; i < (n+1)/2 - 1; i++) a = a.next; //a指針指向連結清單中點
        ListNode b = a.next;  //b指針指向連結清單中點的下一個節點
        while(b!=null) //将連結清單的後半段反向
        {
            ListNode next = b.next; //保留b的next節點
            b.next = a;
            a = b;
            b = next;
        }
        //此時a指向連結清單的尾節點,我們讓b指向連結清單的頭節點
        b = head;
        ListNode tail = a; //保留一下尾節點
        boolean res = true;
        for(int i = 0; i < n/2; i++) //判斷是否是回文連結清單
        {
            if(b.val  != a.val)
            {
                res = false;
                break;
            }
            b = b.next;
            a = a.next;
        }
        //将連結清單複原，後半段連結清單翻轉
        //a指向尾節點，b指向a的下一個節點
        a = tail;
        b = a.next;
        for(int i = 0; i < n/2; i++)
        {
            ListNode next = b.next;
            b.next = a;
            a = b ;
            b = next;
        }
        tail.next = null;
        return res;
    }
}