题解 | #判断一个链表是否为回文结构#

双指针和链表反转

 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
		// write code here
		if (!head || !head->next)return true;
		ListNode* pre, *p = head;
		ListNode* newhead = new ListNode(0);
		while (p&&p->next) {
			p = p->next->next;
			pre = head;
			head = head->next;
			pre->next = newhead;
			newhead = pre;

			
		}

		if (p) {
			head = head->next;
		}
		while (head) {
			if (head->val != newhead->val)return false;
			head = head->next;
			newhead = newhead->next;
		}
		return true;

	}
};