Leetcode234.回文链表(HOT100)

链接

代码：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        // while(slow&&fast){
        //     slow = slow->next;
        //     fast = fast->next;
        //     if(fast)
        //     {
        //         fast = fast->next;
        //     }        
        // }
        while(fast&&fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }

        slow =  reverse(slow);
        fast = head;
        while(fast&&slow){
            if(fast->val!=slow->val){
                return false;
            }
            slow = slow->next;
            fast = fast->next;
        }
        return true;
    }
    ListNode* reverse(ListNode*head){
        ListNode*cur = head;
        ListNode* prev = nullptr;
        while(cur){
            ListNode*k = cur->next;
            cur->next = prev;
            prev = cur;
            cur = k;
        }
        return prev;
    }
};

 我的代码有个缺点：改变了原来的链表，即：将后二分之n长度反转了，如果有需要也可以再reverse回来，届时就不能直接return false，而使用一个flag，break出来，恢复原状之后再return；

其中的reverse方法两次写错：
第一次写错：

    // ListNode* reverse(ListNode*head){
    //     ListNode*cur = head;
    //     ListNode* res = nullptr;
    //     while(cur){
    //         head= cur->next;
    //         cur->next= head->next;
    //         head->next =cur;
    //     }
    //     return res;
    // }

第二次写错：

    // ListNode* reverse(ListNode* root){
    //     if(!root){
    //         return nullptr;
    //     }
    //     ListNode*head = root;
    //     ListNode*p = root;
    //     ListNode*q = root->next;

    //     while(q){
    //         head->next = p->next;
    //         p->next = q->next;
    //         q->next = p;
    //     }
    //     return head;
    // }

 

---

还有一种方法，理解简单但是实现不简单，即：使得后half个节点反转，然后一个指针从头，一个指针从尾，比较half次，比较完之后，恢复原状。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int len = 0;
        for(auto a = head;a;a = a->next)++len;
        if(len<=1) return true;
        int half = len/2;
        auto p = head;
        for(int i = 0;i<len-half;i++)p = p->next;
        auto q = p->next;

        for(int i = 0;i<half-1;i++){
            auto c = q->next;
            q->next = p;
            p = q;
            q = c;
        }

        auto tail = p;
        q = head;
        bool flag = true;
        for(int i = 0;i<half;i++){
            if(q->val!=p->val){
                flag = false;
                break;
            }
            q = q->next;
            p = p->next;
        }

        p = tail;
        auto k = tail->next;
        for(int i = 0;i<half-1;i++){
            auto c = k->next;
            k->next = tail;
            tail = k;
            k = c;
        }
        tail->next = nullptr;
        return flag;
    }
};

 

原文地址：https://blog.csdn.net/kitesxian/article/details/143864995

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！