力扣-234题回文链表（C++）- 链表反转常规函数+双指针+有价值

绝地灬酷狼 2023-01-23 10:56 10阅读 0赞

题目链接：[https://leetcode-cn.com/problems/palindrome-linked-list/][https_leetcode-cn.com_problems_palindrome-linked-list]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
解法一：

/**
     * 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 count=0;
            ListNode* pre=head,*cur=head;
    
            while(pre!=NULL){
        
                count++;
                pre=pre->next;
            }
            if(count==0||count==1) return true;
    
            cout<<count<<endl;
    
            pre=head;cur=head->next;
            int j=(count%2==0)?(count/2-1):(count/2);
    
            for(int i=0;i<j;i++){
        
                pre=cur;
                cur=cur->next;
            }
    
            if(cur!=NULL){
         //排除掉不需要链表反转的情况，如只有两个元素的链表
                auto a=pre,b=cur;
                //反转链表
                while(cur!=NULL){
        
                    ListNode* temp=cur->next;
                    cur->next=pre;
                    pre=cur;
                    cur=temp;
                }
                b->next=NULL;
                a->next=pre;;
            }
            
            cur=head;
            while(pre!=NULL){
        
                if(pre->val==cur->val){
        
                    pre=pre->next;
                    cur=cur->next;
                }
                else return false;
            }
    
            return true;
    
        }
    };

解法二：

/**
     * 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:
        ListNode* reverse(ListNode* head){
        //单链表反转
    
            if(head==NULL||head->next==NULL) return head;       
            ListNode* a=head;
            ListNode* b=head->next;
    
            while(b!=NULL){
        
                ListNode* c=b->next;
                b->next=a;
                a=b;b=c;
            }
            head->next=NULL;
            return a;
            
        }
    
        void print(ListNode* head){
        //输出单链表，仅测试用
    
            for(ListNode* a=head;a;a=a->next) 
            cout<<a->val<<' ';
    
            cout<<endl;
    
        }
        
        bool isPalindrome(ListNode* head) {
        
            //tip：
            //1、计算机在递归的过程中将使用堆栈的空间，递归不是O(1)的空间复杂度。
            //2、1的原因是我在力扣的栈栏下找到的这题，又发现这题好像用不到栈，故此记录小tip。
            int count=0;
    
            for(auto p=head;p;p=p->next) count++;
            if(count==1||count==0) return true;
            if(count%2==0) count=count/2;
            else count=count/2+1;
            
            auto a=head;
            for(int i=0;i<count;i++) a=a->next;
    
            //反转链表
            auto tail=reverse(a);
    
            //判断是否是回文
            bool result=true;
            auto left=head,right=tail;
            while(right!=NULL){
        
                if(left->val!=right->val){
        
                    result=false;
                    break;
                }
                left=left->next;right=right->next;
            }
    
            //恢复链表
            a=reverse(tail);
            tail->next=NULL;
    
            return result;
    
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]

[https_leetcode-cn.com_problems_palindrome-linked-list]: https://leetcode-cn.com/problems/palindrome-linked-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20221004/8e63ac3ae3eb4fc0a2582de8e56923a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]: /images/20221004/47209d2b33314a749edf00350555e0a1.png