关于数据结构与算法: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;
    }
    

}