leetcode 234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

Subscribe to see which companies asked this question

 

这个题是根叔想出来了- - 

刚开始我想的是所有的值存到vector里，然后memory limit exceeded了。

 

后来想怎么都没办法不存啊。

根叔说，把后半部分反转。然后两个链表在从头开始比较。

链表反转刚开始我也不会（PS.我最近智商怎么这么低啊）

 

链表反转，就拿出一个节点然后把它插到头部就可以了。

 

写完了程序，然后一直runtime error~一直找不到原因，后来发现假如你要用到某个指针，就一定要初始化，初始化为NULL啊~

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 
 //反转后半部分链表，然后和前部分链表进行比对
class Solution {
public:
    ListNode* reverse(ListNode *head,int len){    //重新插入逆序
        ListNode* p=NULL,*q=NULL;
        while(len>0){
            q=head->next;
            head->next=p;
            p=head;
            head=q;
            len--;
        }
        return p;
    }
    
    
    bool isPalindrome(ListNode* head) {
        if(head==NULL) return true;
        int len=0,c=0;
        ListNode *p=head,*head1=head;
        while(p!=NULL) {p=p->next;len++;}
        if(len%2==0) c=len/2;
        else c=len/2+1;
        while(c>0) {head1=head1->next;c--;}
        head1=reverse(head1,len/2);
        c=len/2;
        while(c>0){
            c--;
            if(head->val==head1->val) {
                head=head->next;
                head1=head1->next;
                }
            else return false;}
            return true;
    }
};