牛客题目链接 链表的回文结构
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cstdlib>
// 建议大伙自己对照我的代码画下图,假设A链表是:1 2 3 2 1
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) { // 空间复杂度O(1)
// 找到中间节点 (slow是3)
ListNode* slow = A, * fast = A;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// 反转后半部分
//(3 2 1变成1 2 3,但是A并没有变成1 2 1 2 3,A这时是1 2 3,自己画下图就知道了)
ListNode* cur = NULL, * next = NULL;
while (slow) {
next = slow->next;
slow->next = cur;
cur = slow;
slow = next;
}
// 前半部分和后半部分比较 (next = A = 1 2 3,cur = 1 2 3)
next = A;
while (cur) {
if (next->val != cur->val) {
return false;
}
next = next->next;
cur = cur->next;
}
return true;
}
bool chkPalindrome_(ListNode* A) { // 空间复杂度O(n)
// 1.创建B链表,将A链表节点依次向B链表头插
ListNode* B = NULL;
ListNode* curA = A;
while (curA) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = curA->val;
newNode->next = NULL;
if (B == NULL) {
B = newNode;
}
else {
newNode->next = B;
B = newNode;
}
curA = curA->next;
}
// 2.比较
curA = A;
ListNode* curB = B;
while (curA) {
if (curA->val != curB->val) {
return false;
}
curA = curA->next;
ListNode* del = curB;
curB = curB->next;
free(del);
del = NULL;
}
return true;
}
};