【nowcoder】链表的回文结构-Toy模板网

这篇具有很好参考价值的文章主要介绍了【nowcoder】链表的回文结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

牛客题目链接链表的回文结构
【nowcoder】链表的回文结构,Data Structure and Algorithm,C语言,刷题,链表,数据结构,leetcode,算法,c语言文章来源地址https://www.toymoban.com/news/detail-821440.html

/*
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;
    }
};