题目
请判断一个链表是否为回文链表。
示例1
输入: 1->2
输出: false
示例2
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
/** * 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) { if(!head || !head->next) return true; ListNode *fast = head; ListNode *slow = head; ListNode *p, *pre = NULL; // 快慢指针找中间节点 while(fast && fast->next) { p = slow; slow = slow->next; fast = fast->next->next; // 反转 p->next = pre; pre = p; } // 奇数个节点时跳过中间节点 if(fast) slow = slow->next; // 前半部分和后半部分比较 while(p) { if(p->val != slow->val) return false; p = p->next; slow = slow->next; } return true; } }; |
评论