234. Palindrome Linked List（回文链表+O(1)空间）

柔情只为你懂 2023-07-23 12:53 1阅读 0赞

这一题在leetcode中有些许争议，认为题目的描述有问题，因为说了用O（N）时间复杂度和O（1）空间复杂度。点在这个1的空间复杂度。我倾向于认为这个O（1）空间复杂度是指不再使用额外的内存空间。

所以：思路,  
通过让指针走一半的链表，然后将后半部分进行链表逆序，然后从头节点开始一起走。判断相等否。  
需要注意一些细节。一个就是如果链表节点数是奇数的话，后半部分一定要是少的一部分，这样才不会使得前部分走完了，后半部分还有可以走的，使得后部分的第一个节点和最后一个节点相比了。  
另一个细节，当只有一个节点的时候，是回文的。当逆序时如果只有一个节点或者没节点都直接返回第一个节点。  
**最后就是需求是否许后续需要这个链表，如果需要，还要将这个节点逆序回来**  
代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    //想法：链表逆序，然后两个一起走，但是这也就会再用O（N）空间，所以就用去逆序一半的链表就i可
    //回文串，那么一定是偶数
    class Solution { 
    public:
        bool isPalindrome(ListNode* head) { 
            if(head==nullptr || head->next==nullptr)
                return true;
           Node slow,fast;
            slow=head;
            fast=head;                      //一定要让这两个同地出发。确保后面的半截一定较少（奇数时）
            while(fast->next!=nullptr && fast->next->next!=nullptr)         //fast跑在前面，判断它下一个和下下个
            { 
                slow=slow->next;
                fast=fast->next->next;
            }
            slow->next=reverse(slow->next);
            slow=slow->next;
            while(slow!=nullptr)
            { 
                if(head->val!= slow->val)
                    return false;
                head=head->next;
                slow=slow->next;
            }
            return true;
        }
        
        
    private:
        typedef ListNode* Node;
        ListNode* reverse(ListNode* head)
        { 
            if(head==nullptr || head->next==nullptr)            
                return head;
            ListNode* pre=nullptr;
            while(head!=nullptr)
            { 
                ListNode* next;
                next=head->next;
                head->next=pre;
                pre=head;
                head=next;
            }
            return pre;
            
        }
    };