链表回文结构如何改写成长尾？

本文共计350个文字，预计阅读时间需要2分钟。

牛客链接 + 思路：找到中间节点 + 从中间节点开始对后半段进行逆置 + 比较前半段和后半段 + 相等则表示是对称的，否则不是 + 只需将我们之前写过的链表中间节点逆置的代码复用，并加上如下代码即可：

牛客链接

---

思路:

找中间结点

从中间结点开始对后半段进行逆置

比较前半段和后半段

相等是,不相等不是

只需将我们前面写过的链表中间结点,逆置链表的代码复用,并加上如下代码即可

最终代码:

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class PalindromeList { public: //返回中间结点 struct ListNode* middleNode(struct ListNode* head){ struct ListNode*slow,*fast; slow = fast = head; while(fast && fast->next)//考虑到结点个数的奇 { slow = slow->next; fast= fast->next->next; } return slow; } //链表逆置 struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur,*newHead; cur = head; newHead = NULL; while(cur) { struct ListNode* next = cur->next; cur->next = newHead; newHead = cur; cur = next; } return newHead; } bool chkPalindrome(ListNode* head) { struct ListNode* mid = middleNode(head); struct ListNode* rhead = reverseList(mid); while(head && rhead) { if(head->val != rhead->val) return false; head = head->next; rhead = rhead->next; } return true; } };