【初阶数据结构题目】10. 链表的回文结构

链表的回文结构

点击链接做题

思路1：创建新的数组，遍历原链表，遍历原链表，将链表节点中的值放入数组中，在数组中判断是否为回文结构。

例如：

排序前：1->2->2->1

设置数组来存储链表，设置数组头指针left和数组尾指针right

判断left和right指向的数是否相等，相等就left++;right--;，直到left > right

思路代码：

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code hereint arr[900] = {0};int i = 0;ListNode* pcur = A;//遍历链表，将链表中每个节点中的数值储存在数组中while(pcur){arr[i++] = pcur->val;pcur = pcur->next;}//i即结点的个数//找中间节点，判断是否为回文数字int left = 0;//数组头指针int right = i - 1;//数组尾指针while(left < right){if(arr[left] != arr[right]){//不是回文结构return false;}left++;right--;}//是回文结构return true;}
};

思路2：反转链表

1. 找链表的中间节点（快慢指针）
2. 将中间节点之后的链表进行反转
3. 从原链表的头和反转链表比较节点的值

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {public:ListNode* findMidNode(ListNode* phead){ListNode* slow = phead;ListNode* fast = phead;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}ListNode* reverseList(ListNode* phead){ListNode* n1, *n2, *n3;n1 = NULL; n2 = phead, n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3){n3 = n3->next;}}return n1;}bool chkPalindrome(ListNode* A) {// write code here//1.找中间节点ListNode* mid = findMidNode(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;}
};