想法一
先找中间结点，如果为偶数，则指向第二个结点，再把后半段逆置，最后从头进行比对
中间节点：
这段代码在找中间结点那题写过，所以直接拷贝过来
struct ListNode* middleNode(struct ListNode* head) { //要求只遍历一遍链表 struct ListNode* slow = head;//一次走一格 struct ListNode* fast = head;//一次走两格 while (fast->next) { slow = slow->next; fast = fast->next->next; if (!fast) { break; } } return slow; }
逆置：
这段代码也在反转链表时写过，所以直接拷贝过来
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur = head; struct ListNode* rhead = NULL; while (cur) { //头插 struct ListNode* next = cur->next; cur->next = rhead; rhead = cur; cur = next; } return rhead; }
最后，比对才是本题需要做的事情。如果head结点的值与rmid不相等，则不是回文，如果相等，则同时往后一个结点，如果循环结束还没return false，那就证明链表是回文的，return true
bool isPalindrome(struct ListNode* head) { struct ListNode* mid = middleNode(head); struct ListNode* rmid = reverseList(mid); while (rmid) { if (head->val != rmid->val) { return false; } else { head = head->next; rmid = rmid->next; } } return true; }
可能有小伙伴会担心，是奇数个节点的时候，好像head比rmid少一个节点啊？其实，不用担心，因为rmid前的节点还是指向结尾的，如图
所以最后两个指针会共同走到最后一个节点
总结，这是一道糅合了之前多种方法（可以偷懒，cv大法）的题
完整代码：
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur = head; struct ListNode* rhead = NULL; while (cur) { //头插 struct ListNode* next = cur->next; cur->next = rhead; rhead = cur; cur = next; } return rhead; } struct ListNode* middleNode(struct ListNode* head) { //要求只遍历一遍链表 struct ListNode* slow = head;//一次走一格 struct ListNode* fast = head;//一次走两格 while (fast->next) { slow = slow->next; fast = fast->next->next; if (!fast) { break; } } return slow; } bool isPalindrome(struct ListNode* head) { struct ListNode* mid = middleNode(head); struct ListNode* rmid = reverseList(mid); while (rmid) { if (head->val != rmid->val) { return false; } else { head = head->next; rmid = rmid->next; } } return true; }
