回文链表

LeetCode 234 · Easy · 1 min · 榎aaaa

使用的是双指针，以及上面那一题的反转函数

一种比较粗暴的方法是将链表转换成数组，之后再使用双指针从两边向中间遍历比较，但是这个方法的空间复杂度是O(n)

下面这个方法的思路是：找出链表的中点，翻转后半部分，再指定两个指针，分别从首节点与中间节点的后一个节点开始，向后进行遍历比较

那么问题就变成了如何找到链表的中点：

首先定义两个指针：slow指针和fast指针

slow初始指向head，fast初始指向head->next，之后进行循环，slow每次向后移动一位，fast则移动两位，直到fast的下一个节点为空（偶数链表）或fast本身为空（奇数链表），此时可以判断—-slow指向的节点就是前半部分链表的最后一个节点

之后对slow后面的另一半链表进行翻转，再逐个比较即可

 1ListNode* reverse(ListNode* curr, ListNode* prev)
 2    {
 3        if(curr == nullptr) return prev;
 4        ListNode* temp = curr->next;
 5        curr->next = prev;
 6        return reverse(temp, curr);
 7    }
 8
 9    bool isPalindrome(ListNode* head)
10    {
11        ListNode* slow = head;
12        ListNode* fast = head->next;
13        int half = 1;
14
15        while(fast && fast->next)
16        {
17            slow = slow->next;
18            fast = fast->next->next;
19            half++;
20        }
21
22        slow = reverse(slow, nullptr);
23        for(int i = 0; i < half; i++)
24        {
25            if(head->val != slow->val) return false;
26            head = head->next;
27            slow = slow->next;
28        }
29        return true;
30    }