关于数据结构与算法:Linklist经典题目判断回文链表仅使用O1存储空间和On时间复杂度

判断回文链表(仅应用O(1)存储空间和O(n)工夫复杂度)

题目形容
请判断一个链表是否为回文链表,用 O(n) 工夫复杂度和 O(1) 空间复杂度解决。

题目作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetb...
起源：力扣（LeetCode）
题解作者：WildDuck
题目剖析

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */typedef struct ListNode* ListNode_pointer;ListNode_pointer insertAtHead(ListNode_pointer head,ListNode_pointer target){    target -> next = head->next;    head -> next = target;    return head;}bool isPalindrome(struct ListNode* head){    if(head == NULL || head->next == NULL)    {        return true;    }    else     {        ListNode_pointer fast = head;        ListNode_pointer slow = head;                while(fast != NULL && fast->next != NULL)        {            fast = fast->next->next;            slow = slow->next;        }        ListNode_pointer Mid_loc = slow;        //fast 达到开端NULL工夫、slow肯定在原链表两头地位                //头插法逆置后续地位的所有链表        ListNode_pointer new_head = (ListNode_pointer)malloc(sizeof(struct ListNode));        new_head -> next = NULL;        ListNode_pointer temp_new_head = new_head;        ListNode_pointer save_next = NULL;        while(slow != NULL)        {            save_next = slow -> next;            temp_new_head = insertAtHead(temp_new_head,slow);            slow = save_next;        }                slow = head;        temp_new_head = temp_new_head -> next;        while(slow != Mid_loc && slow -> val == temp_new_head ->val)        {            slow = slow -> next;            temp_new_head = temp_new_head -> next;        }        free(new_head);        if(slow == Mid_loc)        {            return true;        }        else return false;    }    }