判断一个链表是否为回文结构
思路
由题可知：回文结构即字符串正序逆序完全一致，如“1 2 3 4 3 2 1”，那么我们就要想办法同时比较链表头和链表尾的元素，看其是否相等。
方法一（快慢指针）
- 定义指针变量left，mid，right，使其分别指向头结点·，头的下一个节点，头的下下个节点。每次同时让left，mid走一个节点，right走两个节点，当right为空，或right的下一个节点为空时，说明right已经走到表尾，此时mid即为链表的中间，令left的指针域为空，即可将链表一分为二。
- 如果链表长度length为偶数，那么翻转以mid为头节点的链表，便于与另一个链表比较。
- 如图：
- 如果链表长度length为奇数，那么就翻转以mid->next为头结点的链表。
- 如图：
- 最后，再将两个链表的元素逐个进行比较，只要出现不相等的情况，直接返回false，若两链表遍历完都没有出现不相等的情况，则返回true
方法一实现代码
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param head ListNode类 the head * @return bool布尔型 */ bool Compare(struct ListNode *head1,struct ListNode *head2) //比较两链表元素 { while(head1 && head2) { if(head1->val != head2->val) return false; head1 = head1->next; head2 = head2->next; } return true; } struct ListNode* Filp(struct ListNode *head) //反转链表 { struct ListNode *newHead = (struct ListNode *)malloc(sizeof(struct ListNode)); newHead->next = head; struct ListNode *pre = newHead, *cur = head; while(cur->next) { struct ListNode *temp = cur->next; cur->next = temp->next; temp->next = pre->next; pre->next = temp; } return newHead->next; } bool isPail(struct ListNode* head ) { if(head == NULL || head->next == NULL) //如果链表只有一个或没有元素，则直接为回文结构，返回true return true; struct ListNode* cur = head; struct ListNode *left = head, *mid = head->next, *right = head->next->next; int count=0; while(cur) { count++; //求出链表长度 cur = cur->next; } while(right && right->next) { left = left->next; mid = mid->next; right = right->next->next; } left->next = NULL; //分割链表 if(count % 2) //判断长度的奇偶 return Compare(head,Filp(mid->next)); else return Compare(head, Filp(mid)); }
方法二（对撞指针）
- 单链表不能逆序遍历，但数组可以呀。因此我们可以遍历链表元素，并将其存入数组中。
- 利用对撞指针的思想，；不断比较数组的头尾元素，只要出现不相等的情况，直接返回false，若遍历完数组都没有出现不相等的情况，则返回true
方法二实现代码
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param head ListNode类 the head * @return bool布尔型 */ bool isPail(struct ListNode* head ) { struct ListNode* cur = head; int count=0; int *num; while(cur) { count++; //求出链表长度 cur = cur->next; } num = (int *)malloc(sizeof(int) * count); //申请数组内存 for(int i = 0;i < count;i++) //将链表数据存入数组 { num[i] = head->val; head = head->next; } for(int i = 0,j = count-1;;i++,j--) //分别从头尾比较数组元素 { if(j <= i) //如果j小于等于i，说明两指针已经相遇，即已经比较完毕，未出现不等情况，直接返回true return true; if(num[i] != num[j]) //只要出现不等的情况，直接返回false return false; } }
