题解 | #判断一个链表是否为回文结构#
判断一个链表是否为回文结构
https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f
双链表法解决,将原链表的后半段翻转。
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 the head * @return bool布尔型 */ #include <stdlib.h> //将后半段数据翻转 struct ListNode* reverse_halfln(struct ListNode* head){ struct ListNode* resl = head; struct ListNode* p = head; struct ListNode* q = head->next; while(q->next!=NULL && q!=NULL){ p = p->next; q = q->next->next; } //start为后半段 struct ListNode* start = p->next; struct ListNode* start_n = start->next; struct ListNode* temp_ln = (struct ListNode*)malloc(sizeof(struct ListNode)); temp_ln->next = NULL; while(start!=NULL){ start->next = temp_ln->next; temp_ln->next = start; start = start_n; if(start != NULL){ start_n = start ->next; } } //防止断链 p->next = temp_ln->next; return resl; } bool isPail(struct ListNode* head ) { // write code here if(head->next == NULL) return true; //翻转后半段得到新的链表 struct ListNode* new_ln = reverse_halfln(head); struct ListNode* p = new_ln; struct ListNode* q = new_ln->next; while(q->next!=NULL && q!=NULL){ p = p->next; q = q->next->next; } //p为后半段开头,q为前半段开头 p = p->next; q = new_ln; while(p!=NULL){ if(p->val!=q->val) return false; p = p->next; q = q->next; } return true; //return true; }