题解 | #判断一个链表是否为回文结构#
判断一个链表是否为回文结构
https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ #include <cstddef> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 the head * @return bool布尔型 */ bool isPail(ListNode* head) { // write code here if (head == NULL) return false; if (head->next == NULL) return true; if (head->next->next == NULL) return false; ListNode* slow = head, * fast = head; stack<int> sk; while (fast) { sk.push(slow->val); slow = slow->next; if (fast->next)fast = fast->next->next; else break; } if (fast) { //奇数 sk.pop(); } while (slow) { if (slow->val != sk.top()) return false; sk.pop(); slow = slow->next; } return true; } };
采用快慢指针的思路,先让慢指针走到链表中间,并用栈记录沿途的值,然后再让慢指针将链表后半部分的值与栈顶元素一一对比。