解题思路:
只要把链表从中间断开,再把其中一个链表反转,就可以依次比较节点值是否相同。
1.寻找链表中间节点,可采用快慢指针,快指针是慢指针速度的两倍,那么,当快指针走到尾部时,慢指针走到链表中间。
2. 反转其中一个链表,之间做过。
class Solution {
public:
ListNode* reverse_list(ListNode* head)
{
ListNode* pre = nullptr;
ListNode* cur = head;
ListNode* temp;
while(cur!=nullptr)
{
temp=cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
bool isPalindrome(ListNode* head) {
if(head==nullptr||head->next==nullptr)
return true;
ListNode * fast = head;
ListNode * slow = head;
ListNode * pre; //记录链表断开的节点,也即是中点的前一个节点
while(fast!=nullptr&&fast->next!=nullptr)
{
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = nullptr; //断开链表
ListNode * cur1 = head; //新链表1
ListNode * cur2 = reverse_list(slow); //新链表2
while(cur1!=nullptr)
{
if(cur1->val!=cur2->val)
return false;
cur1 = cur1->next;
cur2 = cur2->next;
}
return true;
}
};