题解 | #链表的回文结构#

链表的回文结构

http://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa

两种方法,第二种的话空间复杂度成O(N)了;;

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        if(A==NULL)
            return false;
        ListNode* slow=A,*fast=A;
        while(fast && fast->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode* cur=NULL,*next=slow;
        while(slow){
            next=slow->next;
            slow->next=cur;
            cur=slow;
            slow=next;
        }
        next=A;
        while(cur){
            if(next->val!=cur->val)
                return false;
            next=next->next;
            cur=cur->next;
        }
        return true;



        // write code here
//         if(A==NULL)
//             return false;
//         ListNode* cur=A;
//         vector<int> v;
//         while(cur){
//             v.push_back(cur->val);
//             cur=cur->next;
//         }
//         for(int i=0;i<v.size()/2;i++){
//             if(v[i]!=v[v.size()-i-1])
//                 return false;
//         }
//         return true;
    }
};
全部评论

相关推荐

点赞 评论 收藏
分享
10-15 16:27
门头沟学院 C++
LeoMoon:建议问一下是不是你给他付钱😅😅
点赞 评论 收藏
分享
3 收藏 评论
分享
牛客网
牛客企业服务