(链表专题) 234. 回文链表——【Leetcode每日一题】

我不是女神ヾ 2024-03-24 17:00 28阅读 0赞

### 234. 回文链表 ###

给你一个单链表的头节点 `head` ，请你判断该链表是否为回文链表。如果是，返回 `true` ；否则，返回 `false` 。

##### 示例 1： #####

![在这里插入图片描述][537dd61f7dd54d2998a736c1e90ecbe6.png]

> **输入**：head = \[1,2,2,1\]  
> **输出**：true

##### 示例 2： #####

![在这里插入图片描述][273c9136d4b447bf8c7f337e29224a4f.png]

> **输入**：head = \[1,2\]  
> **输出**：false

**提示：**

*  链表中节点数目在范围 \[ 1 , 1 0 5 \] \[1, 10^5\] \[1,105\]内
 *  0 <= Node.val <= 9

#### 思路： ####

题目要求：以 O(1) 的空间复杂度来求解。

**法一：**

*  切成两半，把后半段反转，然后比较两半是否相等

**法二：快慢指针**

*  快慢指针遍历，边遍历，边反转前半部分
 *  然后比较两半是否相等

#### 代码：(Java、C++) ####

**法一：**

**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 len = 0;
            ListNode tem = head;
            ListNode mid = head;
            while(tem != null){
        
                len++;
                tem = tem.next;
                if(len % 2 == 0){
        //找到后半部分头节点
                    mid = mid.next;
                }
            }
            if(len % 2 != 0){
        
                mid = mid.next;
            }
            //将后半部分反转
            ListNode pre = mid;
            mid = null;
            while(pre != null){
        
                tem = pre.next;
                pre.next = mid;
                mid = pre;
                pre = tem;
            }
            for(int i = 0; i < len / 2 && mid != head; i++){
        //比较
                if(head.val == mid.val){
        
                    head = head.next;
                    mid = mid.next;
                }else{
        
                    return false;
                }
            } 
            return true;
    
        }
    }

**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 len = 0;
            ListNode* tem = head;
            ListNode* mid = head;
            while(tem != NULL){
        
                len++;
                tem = tem->next;
                if(len % 2 == 0){
        //找到后半部分头节点
                    mid = mid->next;
                }
            }
            if(len % 2 != 0){
        //如果是奇数个，跳过中间节点
                mid = mid->next;
            }
            //将后半部分反转
            ListNode* pre = mid;
            mid = NULL;
            while(pre != NULL){
        
                tem = pre->next;
                pre->next = mid;
                mid = pre;
                pre = tem;
            }
            for(int i = 0; i < len / 2 && mid != head; i++){
        //比较
                if(head->val == mid->val){
        
                    head = head->next;
                    mid = mid->next;
                }else{
        
                    return false;
                }
            } 
            return true;
        }
    };

**法二：快慢指针**  
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) {
        
            if (head == null || head.next == null) return true;
            ListNode slow = head, pre = head;
            ListNode fast = head;
            head = null;
            while(fast != null && fast.next != null){
        
                slow = slow.next;
                fast = fast.next.next;
                //反转前半部分
                pre.next = head;
                head = pre;
                pre = slow;
            }
            slow = fast != null ? slow.next : slow;//如果是奇数个就跳过中间那个
            while(head != null){
        
                if(head.val == slow.val){
        
                    head = head.next;
                    slow = slow.next; 
                }else{
        
                    return false;
                }
            }
            return true;
    
        }
    }

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) {
        
            if (head == NULL || head->next == NULL) return true;
            ListNode* slow = head;
            ListNode* pre = head;
            ListNode* fast = head;
            head = NULL;
            while(fast != NULL && fast->next != NULL){
        
                slow = slow->next;
                fast = fast->next->next;
                //反转前半部分
                pre->next = head;
                head = pre;
                pre = slow;
            }
            slow = fast != NULL ? slow->next : slow;//如果是奇数个就跳过中间那个
            while(head != NULL){
        
                if(head->val == slow->val){
        
                    head = head->next;
                    slow = slow->next; 
                }else{
        
                    return false;
                }
            }
            return true;
        }
    };

##### 运行结果： #####

![在这里插入图片描述][a0fef92cb9634852b232ed4ed8345bad.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)。
 *  **空间复杂度**： O ( 1 ) O(1) O(1)。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[537dd61f7dd54d2998a736c1e90ecbe6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/e9d6808358b14352bdc21f325e90628d.png
[273c9136d4b447bf8c7f337e29224a4f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/f06c8979bbde451192803e6ec02e08c8.png
[a0fef92cb9634852b232ed4ed8345bad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3649718745f942a2af940301afe8a77c.png
[Link 1]: https://leetcode.cn/problems/palindrome-linked-list/description/
[leetCode]: http://t.csdn.cn/kQLJO