回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路

反转链表，然后与原来相比较

bool isPalindrome(struct ListNode* head) {
    
    if(head==NULL||head->next==NULL){
        return true;
    }
    struct ListNode* node=head;
    struct ListNode* newHead=NULL;

    while(node!=NULL){
        struct ListNode* temp=(struct ListNode* )malloc(sizeof(struct ListNode));
        
        temp->val=node->val;
        temp->next=newHead;
        newHead=temp;
        
        
        node=node->next;
    }
    
    while(newHead!=NULL){
        if(newHead->val==head->val){
            newHead=newHead->next;
            head=head->next;
        }else{
            return false;
        }
    }
    return true;

思路

遍历链表，每个节点的值放在数组上，然后用快慢指针的方法判断该数组是否回文

bool isPalindrome(struct ListNode* head) {
   struct ListNode* temp=head;
    int i=0;
    while(temp!=NULL){
        temp=temp->next;
        ++i;
    }
    int a[i];
    for(int j=0;j<i;++j){
        a[j]=head->val;
        printf("%d",a[j]);
        head=head->next;
    }
    int start=0;
    int end=i-1;
    while(start<end){
        if(a[start]==a[end]){
            start++;
            end--;
        }else{
            return false;
        }
    }
    return true;
}

思路

用快慢指针法，fast一次走两步，slow一次走一步，等fast走到末尾，slow就在中间节点(这里分节点个数为奇数还是偶数)，之后之后反转slow，与head相比

bool isPalindrome(struct ListNode* head) {
    
  if(head==NULL||head->next==NULL){
      return true;
  }
    
    struct ListNode* fast=head;
    struct ListNode* slow=head;
    
    
    while(fast!=NULL&&fast->next!=NULL){
        fast=fast->next->next;
        slow=slow->next;
    }
    struct ListNode* temp=NULL;
    struct ListNode* newHead=NULL;
    while(slow!=NULL){
        temp=slow->next;
        slow->next=newHead;
        newHead=slow;
        slow=temp;
    }
    fast=head;
    while(fast!=NULL&&newHead!=NULL){
        if(fast->val!=newHead->val){
            return false;
            
        }
        fast=fast->next;
        newHead=newHead->next;
        
    }
    return true;   
}