题解 | #链表的回文结构#
链表的回文结构
https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa
class PalindromeList {
public:
struct ListNode* prevnode(struct ListNode*head)
{
struct ListNode*n1,*n2,*n3;
n1 = nullptr;
n2 = head;
n3 = head->next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3)
n3 = n3->next;
}
return n1;//返回逆置后的链表头节点
}
struct ListNode* Midnode(struct ListNode *phead)
{
struct ListNode*quick,*slow;
quick = slow = phead;
while(quick && quick->next)
{
quick = quick->next->next;
slow =slow->next;
}
return slow;//返回中间节点
}
bool chkPalindrome(ListNode* A) {
struct ListNode*Mid = Midnode(A);
struct ListNode*pMid = prevnode(Mid);
while(A && pMid)
{
if(A->val != pMid->val)
{
return false;
}
A = A->next;
pMid = pMid->next;
}
return true;
}
};
