LeetCode-234. 回文链表(C语言）

数据结构复习到了链表，顺便也把这个题解了
leet上最快的解题是把链表的内容复制到数组，然后从数组两端比较

我的解法只使用了链表，所以会慢于数组解法

思路：

1. 使用快慢指针来确定链表的中间位置，慢指针每次走一步，快指针走两步
   如果是ABCD偶数个元素情况，慢指针最后会指向B；快指针由于初始化时提前移动了一位（即初始化时慢指针指向A，快指针指向B），所以快指针最后指向D
   如果是ABCDE奇数个情况，慢指针恰好指向中点C，快指针指向E
2. 将慢指针之后的链表断开（或者视为两个链表），然后对后半链表进行逆反操作
3. 对两部分链表从头开始比较，如果有不同则不是回文链表。
4. 对后半部分链表再次进行逆操作，恢复原顺序，再将前半链表和后半链表链接起来，恢复初始状态。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverse_list(struct ListNode *list)
{//abc -> cbastruct ListNode *tail = list;struct ListNode *ptr = list;struct ListNode *fast;while(tail->next != NULL)tail = tail->next;while(ptr != tail){fast = ptr->next;ptr->next = tail->next;tail->next = ptr;ptr = fast;}return tail;
}
bool processing(struct ListNode *list,const int length)
{if(list == NULL)return false;bool re = true;struct ListNode *slow = list;struct ListNode *fast = list;if((length & 1) == 0)fast = fast->next;//提前走一步 为了找到tailwhile (fast->next != NULL){slow = slow->next;fast = fast->next->next;}struct ListNode *middle_left = slow;slow = slow->next; //中后的第一个位置struct ListNode *new_head = reverse_list(slow);slow = new_head;fast = list;while (slow != NULL){if (slow->val != fast->val){re = false;break;}slow = slow->next;fast = fast->next;}//恢复listnew_head = reverse_list(new_head);middle_left->next = new_head;return re;
}
bool isPalindrome(struct ListNode* head) {struct ListNode* ptr = head;int length=0;while(ptr!=NULL){++length;ptr = ptr->next;}if(length<=1)return true;return processing(head,length);}