234.回文链表

题目来源：力扣https://leetcode.cn/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/

题目简介：简单的就是判断一个链表是否为回文链表

双指针

思路：首先就是可以想到用个双指针一个指头，一个指尾巴。判断两个指的val相等不相等就完事了。但这里这个初始状态为链表就有点不太好搞，链表指后一个结点还简单，指向前一个结点就会有点麻烦，所以就可以先把这个链表转化为顺序表，顺序表就可以用for循环来--或者++来移动指针，所以整体分为两个步骤；1.把链表元素都先复制到顺表表里去；2.再用双指针比较两个指针的值

代码段：

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

递归思路：

首先对于链表天然的递归规则对于递归写法来说，是必然的。然后就是对于这个题的回文性质，和递归里的归的性质是很像的。我们就可以用递归的方法，在链表表头设置一个指针，然后在递完以后，每归一次，表头的指针就往后移动一下，在移动前还可以进行比较首尾的节点值，就可以巧妙的避开创造多余的空间，降低空间复杂度。

代码段：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 struct ListNode* frontPointer;
 bool recursivelyCheck(struct ListNode* currentNode){
     if(currentNode!=NULL){
         if(!recursivelyCheck(currentNode->next)){
             return false;
         }
         if(frontPointer->val!=currentNode->val){
             return false;
         }
         frontPointer=frontPointer->next;
     }
     return true;
 }
bool isPalindrome(struct ListNode* head){
    frontPointer=head;
    return recursivelyCheck(head);
}

快慢指针：

回文链表实际上是后部分的链表反转以后和前半部分链表的每个节点值一样。所以我们只需要遍历到这个链表的中间位置，然后把后半部分链表反转，然后比较前后两部分链表每个位置结点值。

总体分为五个步骤。（精华就在设置快慢指针，快指针的遍历速度是慢指针的两倍。使得慢指针停在中间结点）

1.先找到中间结点。

2.反转后部分链表。

3.比较前后链表。

4.还原链表

5.返回结果

代码段：

//反转链表
struct ListNode* reverseList(struct ListNode* head){
     if(head==NULL||head->next==NULL){
         return head;
     }
     struct ListNode* Newhead=reverseList(head->next);
     head->next->next=head;
     head->next=NULL;
     return Newhead;
 }
//快慢指针遍历
 struct ListNode* endOfFirstHalf(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
 
bool isPalindrome(struct ListNode* head) {
    if (head == NULL) {
        return true;
    }
 
    // 找到前半部分链表的尾节点并反转后半部分链表
    struct ListNode* firstHalfEnd = endOfFirstHalf(head);
    struct ListNode* secondHalfStart = reverseList(firstHalfEnd->next);
 
    // 判断是否回文
    struct ListNode* p1 = head;
    struct ListNode* p2 = secondHalfStart;
    bool result = true;
    while (result && p2 != NULL) {
        if (p1->val != p2->val) {
            result = false;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
 
    // 还原链表并返回结果
    firstHalfEnd->next = reverseList(secondHalfStart);
    return result;
}