回文链表
回文结构即字符串正序逆序完全一致，如“1 2 3 4 3 2 1”，那么我们就要想办法同时比较链表头和链表尾的元素，看其是否相等。
下面介绍一种最常用的方法：
思路
如果我们仔细观察回文结构，就会得到一个结论：
将一个回文结构从正中间分隔，再将后半部分逆序，那么前半部分就一定等于后半部分。
我们可以分链表长度为奇数和偶数讨论：
当长度为偶数：
当长度为奇数：
- 那么**，第一步就先要得到链表的中间节点。我们可以用快慢指针**来实现：
定义两个指针fast、slow，同时指向链表头，slow每次走一个，fast每次走两个节点，当fast->next == NULL 或者 fast == NULL时，slow就走到中间节点了
struct ListNode* slow = head; struct ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
- 第二步，就是反转以
slow节点为头的链表，如果对单链表反转还不太了解的朋友，建议先看看👉反转单链表
struct ListNode* reverseList(struct ListNode* head) { if (head == NULL) return NULL; struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode)); newHead->next = head; struct ListNode* cur = head; while (cur->next) { struct ListNode* curNext = cur->next; cur->next = curNext->next; curNext->next = newHead->next; newHead->next = curNext; } struct ListNode* retHead = newHead->next; free(newHead); return retHead; }
- 第三步，我们用指针
mid来接受slow后链表反转过后的头，接下来，从原来链表的头和mid开始比较，只要遇到不相等的情况，就返回false，否则返回true。
struct ListNode* mid = reverseList(slow->next); struct ListNode* cur1 = head; struct ListNode* cur2 = mid; while (cur1 && cur2) { if (cur1->val != cur2->val) { return false; } cur1 = cur1->next; cur2 = cur2->next; } return true;
- 最后一步，**在返回之前，需要将链表还原，**毕竟在现实生活中，没有人想再调用这个函数时改变原来的链表结构。但是，如果我们就按上面的操作进行还原，那么就会出现一系列的问题，我们拿下图说明
判断过后，链表的结构是这样的：
如果我们要将链表还原，那么问号处的节点的后面应该链接到reverseList(mid)的返回值，但问题是之前我们并没有保存问号处的节点。所以，我们可以对找到链表中间节点这一操作进行改进：
struct ListNode* slow = head; struct ListNode* fast = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; }
这样slow就会停留在问号处的位置，反转链表的时候就反转以slow->next为头的链表就行了
实现代码
struct ListNode* reverseList(struct ListNode* head) //反转链表 { if (head == NULL) return NULL; struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode)); newHead->next = head; struct ListNode* cur = head; while (cur->next) { struct ListNode* curNext = cur->next; cur->next = curNext->next; curNext->next = newHead->next; newHead->next = curNext; } struct ListNode* retHead = newHead->next; free(newHead); return retHead; } bool isPalindrome(struct ListNode* head){ struct ListNode* slow = head; struct ListNode* fast = head; while (fast->next && fast->next->next) //找到中间节点的前一个节点 { slow = slow->next; fast = fast->next->next; } //反转以中间节点为头的链表 //将返回值赋给mid struct ListNode* mid = reverseList(slow->next); struct ListNode* cur1 = head; struct ListNode* cur2 = mid; bool ret = true; //设置返回值 while (cur1 && cur2) { if (cur1->val != cur2->val) { ret = false; //只要出现不相等的情况，就将返回值设为false，推出比较 break; } cur1 = cur1->next; cur2 = cur2->next; } //还原链表 mid = reverseList(mid); slow->next = mid; //返回 return ret; }
