单链表算法实战：解锁数据结构核心谜题——链表的回文结构

题目如下：

解题过程如下：

回文结构举例：
回文数字：12521、12321、1221……
回文字符串：“abcba”、“abba”……

并不是所有的循环嵌套的时间复杂度都是O(n^2)

可以用C++写C程序：

C++里可以直接使用ListNode作为结构体类型名：

思路1：新建一个单链表，保存原来链表的结点，反转新链表，遍历这两个链表比较结点是否相同。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        //新建一个单链表，保存原链表的结点，反转新链表
        ListNode* n1, *n2, *n3;
        n1 = NULL, n2 = A, n3 = n2->next;
        while (n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3)
            {
                n3 = n3->next;
            }
        }
        //遍历这两个链表，比较这两个链表中的结点数值是否相等
        while (A && n1)
        {
            if (A->val == n1->val)
            {
                A = A->next;
                n1 = n1->next;
            }
            else 
            {
                return false;
            }
        }
        return true;
    }
};

思路2：创建一个数组（大小900），遍历原链表将结点中的数值依次存储在数组中，判断数组是否为回文结构。

创建一个数组，有900个空间，空间复杂度：O(900) == O(1)

i表示存储的结点中数据的个数（数组中有效数据的个数）

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        //新建一个数组（大小900）
        int arr[900] = { 0 };
        //遍历单链表，将链表结点中的数值依次存储在数组中
        ListNode* pcur = A;
        int i = 0;
        while (pcur)
        {
            arr[i++] = pcur->val;
            pcur = pcur->next;
        }
        //判断数组是否是回文结构
        int left = 0, right = i - 1;
        while (left < right)
        {
            if (arr[left] != arr[right])
            {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

题干没有“保证链表长度小于等于900”这句话，思路2不适用。

思路3：找到链表的中间结点（快慢指针），中间结点作为新链表的头结点然后反转链表，比较两个链表里的值是否相等。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        //找到链表的中间结点(快慢指针)
        ListNode* slow, *fast;
        slow = fast = A;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        //中间结点作为新链表的头结点，反转新链表
        ListNode* n1, *n2, *n3;
        n1 = NULL, n2 = slow, n3 = n2->next;
        while (n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3)
            {
                n3 = n3->next;
            }
        }
        //比较两个链表中的结点存储的数值
        ListNode* newHead = n1;
        ListNode* head = A;
        while (newHead && head)
        {
            if (newHead->val != head->val)
            {
                return false;
            }
            head = head->next;
            newHead = newHead->next;
        }
        return true;
    }
};

思路3代码完善：找链表的中间结点和反转链表可以分别封装成一个函数实现。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    ListNode* middleNode(ListNode* head)
    {
        ListNode* slow, *fast;
        slow = fast = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* reverseList(ListNode* head)
    {
        if (head == NULL)
        {
            return NULL;
        }
        ListNode* n1, *n2, *n3;
        n1 = NULL, n2 = head, n3 = n2->next;
        while (n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3)
            {
                n3 = n3->next;
            }
        }
        return n1;
    }
    bool chkPalindrome(ListNode* A) {
        //1.找到链表的中间结点
        ListNode* mid = middleNode(A);
        //2.中间结点作为头结点，反转链表
        ListNode* right = reverseList(mid);
        //3.比较两个链表的结点里的值是否相等
        ListNode* left = A;
        while (right)
        {
            if (left->val != right->val)
            {
                return false;
            }
            left = left->next;
            right = right->next;
        }
        return true;
    }
};