1. 题目
请判断一个链表是否为回文链表。示例 1:
输入: 1->2输出: false示例 2:输入: 1->2->2->1
输出: true进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
2. 思路
- 此题可以看做是 和 的结合。
定义快慢两个指针，寻找中间结点，同时在慢指针移动的过程中反转前半部分子链表。当找到中间结点时，再分别向前向后比较前后两个子链表的每一个结点值是否相同。
- 偶数结点情况如下
- 此时，我们分别得到了以 slow 为头指针的前半部分子链表和以 p2 为头指针的后半部分子链表。由于中间结点偏向后边，所以我们需要先比较最中间的两个结点（此处为 2 和 3 结点），然后再依次向两边循环比较直到到达子链的链尾。
- 再来看奇数结点的情况
- 奇数个结点时，我们依然可以分别得到以 slow 为头指针的前半部分子链表和以 p2 为头指针的后半部分子链表。此时，由于 slow 指向的中间结点无须比较，我们只需从 slow 后面第一个结点和 p2 指向的结点开始循环向两边比较即可（此处为 2 和 4 结点）。
/** * 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 == NULL || head->next == NULL) // 空链或只有一个结点，返回 true { return true; } else { /* 此为反转链表的三个指针，slow 即代表 p1 */ ListNode* slow = head; // 慢指针指向第一个结点 ListNode * p2 = slow->next; // 第二个结点 ListNode * p3 = p2->next; // 第三个结点 ListNode* fast = head; // 快指针指向头结点 // 奇数结点快指针指向最后一个结点结束 // 偶数结点快指针指向 NULL 结束 while(fast && fast->next) { p3 = p2->next; fast = fast->next->next; // 快指针前进两步 p2->next = slow; // 反转链表 slow = p2; // 慢指针前进一步 p2 = p3; } head->next = NULL; // 处理前半部分子链的尾节点 // 偶数结点 if(!fast) { // 先比较 slow 后的两个结点是否相同 if (slow->val == slow->next->val) { // 以 slow 后的第三个结点和 p2 指向的结点开始循环向两边比较 slow = slow->next->next; while(slow) { if (slow->val != p2->val) { return false; } else { slow = slow->next; p2 = p2->next; } } return true; } else { return false; } } // 奇数结点 else { // 以 slow 后的第一个结点和 p2 指向的结点开始循环向两边比较 slow = slow->next; while(slow) { if (slow->val != p2->val) { return false; } else { slow = slow->next; p2 = p2->next; } } return true; } } }}; 获取更多精彩，请关注「seniusen」!
