【C语言】实战-力扣题库：回文链表

题目描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

问题分析

O(1)的时间复杂度---跟n不产生关系

        因为链表只能比较当前值和next域的值，因此我们把链表中的值导入到数组当中进行比较。

我的解法：

比较前面和后面的值，两个指针同时往中间走进行比较。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool isPalindrome(struct ListNode* head) {
   int arr[100000];
   int index=0;
   struct ListNode* flag=head;
   while(flag!=NULL){
        arr[index]=flag->val;
        index++;
        flag=flag->next;
   }
   
   int i=0;
   int j=index-1;
   for(;i<j;){
        if(arr[i]==arr[j]){
            i++;
            j--;
        }else{
            return false;
        }
        
   }
   return true;
}

另一种解法：

快慢指针能够找到链表中间位置，也能判断链表是否有环。

一个走一步，一个走两步

后面的链表翻转，比较两段链表的值。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool isPalindrome(struct ListNode* head) {
   if(head==NULL||head->next==NULL){
    return true;
   }
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    //后半段翻转
    struct ListNode* h=NULL;
    struct ListNode* f=slow;
    while(f!=NULL){
        struct ListNode* w=f->next;
        f->next=h;
        h=f;
        f=w;
    }
    //比较两个链表
    while(h!=NULL){
        if(head->val!=h->val){
            return false;
        }
        head=head->next;
        h=h->next;
    }
    return true;


}