之前腾讯WXG一面考过这个题,要求的就是这种解法,一个题包含三个部分。
class Solution {
public:
ListNode* middle(ListNode* head) //快慢指针找链表中点
{
auto fast = head, slow = head;
while (fast->next && fast->next->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
ListNode* reverse(ListNode* head) //反转链表
{
if (head == nullptr) return nullptr;
auto pre = head, cur = head->next;
while (cur)
{
auto ne = cur->next;
cur->next = pre;
pre = cur, cur = ne;
}
head->next = nullptr;
return pre;
}
bool is_same(ListNode* L1, ListNode* L2) //判断两链表是否相同
{
auto p1 = L1, p2 = L2;
while (p2) //注意此处必须判断p2是否为空,不能判断p1,因为当给定链表长度为1时,
{ //p2是空的,对p2取值:p2->val会报错,所以必须先对p2判空
if (p1->val != p2->val) return false;
p1 = p1->next;
p2 = p2->next;
}
return true;
}
bool isPalindrome(ListNode* head) {
if (head == nullptr) return true;
auto mid = middle(head); //找到中点
auto p1 = head, p2 = reverse(mid->next); //反转链表后半部分
return is_same(p1, p2); //比较链表的前半部分与后半部分
}
};