【leetcode】234. 回文链表（palindrome-linked-list）（双指针）[简单]

链接

https://leetcode-cn.com/problems/palindrome-linked-list/

耗时

解题：15 min 题解：5 min

题意

请判断一个链表是否为回文链表。

进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路

原地翻转链表的前半部分，然后比较 翻转后的前半部分 和 链表的后半部分 是否相同。

时间复杂度：$O(n)$

AC代码

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool isPalindrome(ListNode* head) { int n = 0; ListNode* cnt = head; while(cnt != NULL) { cnt = cnt->next; n++; } if(n <= 1) return true; ListNode* rhead = head; ListNode* curr = head->next; head->next = NULL; for(int i = 0; i < n/2-1; ++i) { ListNode* post = curr; curr = curr->next; post->next = rhead; rhead = post; } if(n&1) curr = curr->next; while(curr != NULL) { if(curr->val != rhead->val) { return false; } curr = curr->next; rhead = rhead->next; } return true; } };