面试题 02.06. 回文链表

回文链表"/>

面试题 02.06. 回文链表

​题目来源：

        leetcode题目，网址：面试题 02.06. 回文链表 - 力扣（LeetCode）

解题思路：

       快慢指针，快指针指向第二个节点，慢指针指向第一个节点。然后快指针每次向后移动两个节点，慢指针向后移动一个节点的同时翻转前面的链表。最后遍历前半个链表和后半个链表比较即可。

解题代码：

/*** 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==nullptr || head->next==nullptr){return true;}ListNode* pre=nullptr;ListNode* slow=head;ListNode* quick=head->next;ListNode* formor=nullptr;ListNode* latter=nullptr;while(quick!=nullptr){quick=quick->next;ListNode* temp=slow->next; slow->next=pre;pre=slow;slow=temp;if(quick==nullptr){latter=slow;formor=pre;}else{quick=quick->next;if(quick==nullptr){latter=slow->next;formor=pre;}}}while(formor!=nullptr){if(formor->val!=latter->val){return false;}formor=formor->next;latter=latter->next;}return true;}
};

总结：

        官方题解给出了三种解法。第一种是复制到数组中后用双指针。第二种是递归比较。第三种是快慢指针。