题目要求

链接：链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

---

1 -> 2 -> 3 -> 2 -> 1

1 -> 2 -> 2 -> 1

上面两个是回文结构

---

方法1：思路

• 1.遍历链表，把结点对应的值放到数组中。
• 未知数组的大小
  • 法1：直接设置900个空间(题目中已经说明链表长度小于等于900)
  • 法2：遍历链表求出链表的长度，然后再对应开辟数组 ->效率低，不选用
• 2.判断链表回文->转化成判断数组元素是回文的
  • 双指针
  • 定义头尾指针进行比较，left指针指向最左边，right指针指向最右边。二者指向的元素比较
    • a[left] = a[right] ==> left++ right–
    • a[left] != a[right] ==> return false
  • 循环结束条件：left < right (不取等，当二者指向相同的元素/left > right 说明已经是回文结构了)
  • 若比较完成，退出循环，说明是回文结构。
• 时间复杂度：0(N)

---

图解

---

代码

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code here//空链表==>不是回文结构if(A == NULL){return false;}//存放到数组中int arr[900];//题目说了，链表长度小于等于900int sz = 0;//标志数组元素//遍历链表，存放元素到数组中struct ListNode* curA = A;while(curA){//放到sz位置上，然后sz++arr[sz++] = curA->val;//curA指向下一个结点curA = curA->next;}//对数组元素进行判断是否是回文结构int left = 0;int right = sz - 1;//最后一个元素while(left < right){if(arr[left] != arr[right]){return false;}left ++;right --;}//数组元素比较完成，说明数组是回文结构  -> 链表是回文的return true;}
};

---

方法2

• 1.找到链表的中间结点(使用快慢指针)，记为mid
• 2.将mid到尾结点部分链表进行反转 (使用三指针n1,n2,n3)，返回新的头记为rhead
  • n1:初始化为空 ,n2反转要指向的结点
  • n2:要反转的结点
  • n3:保存n2的下一个结点，防止找不到
• 3.遍历比较[head,rhead)结点 和 [rhead,尾结点] 结点
  • 为了保留两个头结点位置，定义新的变量进行遍历，
  • curA 遍历[head,rhead] curR 遍历[rhead,尾结点]
  • 如果curA和curB指向结点的值不相同 ->不是回文
• 循环结束条件：curA 或者curB其中一个为空 (curA && curB)
• 能跳出循环，说明curA和curB指向的值全都相等 ->是回文

---

图解：

• 偶数个结点

  

• 奇数个结点

  

• 非回文

---

注意：反转之前的mid的前一个结点的next仍指向原来的位置

---

代码

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*///找链表的中间结点 - 快慢指针
struct ListNode* MidNode(struct ListNode* head)
{if(head == NULL){return NULL;}struct ListNode* slow = head;struct ListNode* fast = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;
}//反转链表
struct ListNode* ReverseList(struct ListNode* head)
{//只有一个结点/链表为空不用反转if(head == NULL || head->next == NULL){return head;}struct ListNode*n1= NULL,*n2 = head,*n3 = head->next;while(n2){// 反转n2 ->next = n1;//迭代往后走n1 = n2;n2 = n3;//防止n3为空时还往后走，对空指针解引用if(n3 != NULL){n3 = n3->next;}}return n1;
}
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code hereif(A == NULL){return false;}//找中间结点struct ListNode* mid = MidNode(A);//反转中间结点后面的内容struct ListNode* rhead = ReverseList(mid);//遍历前后两部分链表struct ListNode* curA = A;struct ListNode* curR = rhead;while(curA && curR)//while(curR)可以 //while(curA)不可以{if(curA->val != curR->val){return false;}curA = curA->next;curR = curR->next;}return true;}
};

---

为什么判断条件while(curR)可以,while(curA)不可以？

以上面图解的例子

若以curA为循环结束条件，即当curA指向NULL时才跳出循环，像上面这种情况，curR已经指向空了，再进入循环，就是对空指针进行访问了，出错

若以curR为循环结束条件是可以的

若是回文结构：奇数个结点时：curA和curR同时指向NULL结束 偶数个结点时：curR比curA先指向NULL结束

若不是回文，二者都不会走到NULL，比较时就返回false了

所以循环条件可以写成：while(curA&& curR) ->含义时：curA和curR都不为空就继续，其中一个为空就跳出循环

也可以写成while(curR)

但是不可以写成while(curA)

---