234. 回文链表 - 力扣（LeetCode）

递归方案

void traverse(ListNode* head) {// 前序遍历代码traverse(head->next);// 后序遍历代码
}

链表兼具递归结构，树结构不过是链表的衍生。链表其实也可以有前序遍历和后序遍历

如果我想正序打印链表中的 val 值，可以在前序遍历位置写代码；

反之，如果想倒序遍历链表，就可以在后序遍历位置操作

class Solution {
public:ListNode* left;bool isPalindrome(ListNode* head) {left = head;return traverse(head);}// bool ans = true;bool traverse(ListNode* right) {if(!right) return true;bool ans = traverse(right->next);ans = ans && (left->val == right->val);left = left->next;return ans;}
};

实际上就是把链表节点放入一个栈，然后再拿出来，这时候元素顺序就是反的，

只不过我们利用的是递归函数的堆栈而已

双指针方案（快慢指针 / 左右指针）

快慢指针找中点的特点

=> 当链表长度为奇数时：slow指向中点，fast指向最后一个结点

     当链表长度为偶数时：slow指向中间两个的后面一个，fast指向NULL

然后再利用左右指针从两端到中心进行回文判断

class Solution {
public:bool isPalindrome(ListNode* head) {ListNode* fast = head, *slow = head;while(fast && fast->next) {fast = fast->next->next;slow = slow->next;}// 当链表长度为奇数时，slow位于中点（让slow向后移一位）// 当链表长度为偶数时，slow位于中间两个的后面一个（正是我们想要的）if(fast != NULL) slow = slow->next;ListNode* right = reverse(slow);ListNode* left = head;// while的条件很巧妙，因为反转后右指针遍历最后一个结点后就是NULLwhile(right) {if(left->val != right->val) return false;left = left->next;right = right->next;}return true;}private:ListNode* reverse(ListNode* head) {ListNode* pre = NULL, *cur = head;while(cur != NULL) {ListNode* next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;}
};

如果我最终不能破坏链表结构呢（或者说保证完成任务前面链表一致）

odd时候：p指向的链表中点；

even时候：p指向链表中间两个的前一个；

while(fast && fast->next) {if(fast->next == NULL) p = slow;// oddif(fast->next->next == NULL) p = slow;// evenfast = fast->next->next;slow = slow->next;
}// ...ListNode* q = right;p->next = reverse(q);