题解 | #链表的回文结构#

/*
	空间复杂度O(1)，所以只能原地操作。
	想法：
		将链表分成两半，然后逆置其中一半，接着遍历判断两半链表是否相等。
		（采用快慢指针的方式，找到链表中点，然后将链表两半各拼到两个头节点后面，形成两个链表。
		  快指针为空，则个数为偶数，反之则为奇数）
	注意点：
		要区分链表个数为奇数还是偶数。
		将节点放到带头链表中，最后要注意抛弃头节点。
		要将前一个链表的末尾置空。
	细节：
		当节点个数为偶数时，[0,s-1], [s,f-1]
		当节点个数为奇数时，[0,s-1], [s+1,f]
		所以仅有后半段不同，处理节点个数为奇数时，先将cur向后一位，再将后续节点放到第二个链表中。
		偶数时的f-1和奇数时f都是链表尾节点，没有区别。
*/
class PalindromeList {
  public:
    bool chkPalindrome(ListNode* head) {
		// 快慢指针找中点
        ListNode* slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
		
		// 分到两个链表中
        ListNode* head1 = new ListNode(-1), *cur1 = head1;
        ListNode* head2 = new ListNode(-1), *cur2 = head2;
        ListNode* cur = head;

        while (cur != slow) {
            cur1->next = cur;
            cur1 = cur1->next;
            cur = cur->next;
        }
        cur1->next = nullptr;

        if (fast) { // 奇数个元素 [0, s-1] [s+1, f]
            cur = cur->next;
        } // else 偶数个元素 [0,s-1] [s, f-1]

        while (cur) {
            cur2->next = cur;
            cur2 = cur2->next;
            cur = cur->next;
        }
		
		// 逆置其中某个链表
        cur = head1->next;
        ListNode* prev = nullptr;
        while (cur) {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }

		// 设置好起点，遍历对比
        cur1 = prev;
        cur2 = head2->next;

        while (cur1) {
            if (cur1->val != cur2->val) {
                return false;
            }
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return true;
    }
};