234、回文链表

题目：

解答：

对143稍作修改即可，判断两个指针指向的是否一直相等。

终止条件为不等或者head2=nullptr

class Solution {
public:ListNode *rev(ListNode *head){ListNode *cur = head;ListNode *pre = nullptr;while(cur){ListNode * nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;}return pre;}ListNode *midd(ListNode *head){ListNode *fast = head;ListNode *slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;}bool isPalindrome(ListNode* head) {ListNode *mid = midd(head);ListNode *head2 = rev(mid);while(head2){if(head->val != head2->val)return false;head=head->next;head2=head2->next;}return true;}
};

时间复杂度O(n)

空间复杂度O(1)