Sword finger offer II 027 Palindrome linked list

In daily question brushing

GitHub link

diwei00 (github.com)https://github.com/diwei00 All the codes are in Exercise Submit in Library

LeetCode link

The finger of the sword Offer II 027. Palindrome list - Power button （LeetCode）https://leetcode.cn/problems/aMhZSa/

subject

Given a linked list   Head node  head , Please judge whether it is a palindrome linked list .

If a linked list is palindrome , Then the list node sequence is the same from front to back and from back to front .

Example 1

 Input : head = [1,2,3,3,2,1]
 Output : true

Example 2

 Input : head = [1,2]
 Output : false

title 🤨

      First , The palindrome linked list is judged by comparing the data of the first node with the data of the last node , Then compare the data of the second node and the penultimate node , And so on . Because this is a single linked list , It doesn't have random access to data like a sequence table , You can only traverse the linked list from front to back .

      Analyze the topic and find , Data comparison is to compare the first half and the second half of the linked list , So we need to find the middle node of the linked list . Because the comparison is made between the first half of the node data and the second half of the node data , So consider reversing the second half of the linked list .

      Find the middle node of the linked list here , It uses the fast and slow pointer method , Go two steps at a time , Slow pointer one step at a time . Distinguish between even and odd node linked lists , When the fast pointer traverses the linked list , The slow pointer is just in the middle node of the linked list .

      Here, reverse the linked list , The three pointer method is used , In order to find the next node after reversing .

The two ideas here are introduced in detail in this blog .

Reverse a linked list （AND） The middle node of a list _ Little astronaut w The blog of -CSDN Blog https://blog.csdn.net/weixin_62353436/article/details/124332827?spm=1001.2014.3001.5501

Code implementation （ There are detailed notes ）

bool isPalindrome(struct ListNode* head)
{
    struct ListNode* phead = head;
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    // The speed pointer finds the middle node 
    while (fast != NULL && fast->next != NULL)
    {
      
        fast = fast->next->next;
        slow = slow->next;
    }
    struct ListNode* p1 = NULL;
    struct ListNode* p2 = slow;
    struct ListNode* p3 = slow->next;
    // Reverse the second half of linked list 
    while (p2 != NULL)
    {
        p2->next = p1;
        p1 = p2;
        p2 = p3;
        if (p3 != NULL)
        {
            p3 = p3->next;
        }
    }
    // Comparison data 
    while (p1 != NULL)
    {
        if (p1->val == phead->val)
        {
            p1 = p1->next;
            phead = phead->next;
            
        }
        else
        {
            return false;
        }
    }
    // All data are equal 
    return true;
}

Summary

    For the operation of linked list , Consider that accessing data is different from sequential tables , So there will be some differences in thinking . We need to brush a lot of questions , Exercise programming thinking ,  I believe that persistence will lead to different results 🤨.