示例 1:
输入: 1->2 输出: false
示例 2:
输入: 1->2->2->1 输出: true
分析找出链表的中间结点,将中间结点以后的结点逆置,比较原链表和逆置后的链表即可得出结果
struct ListNode* slow=head; struct ListNode* fast=head; if(head==NULL ) return 1; while(fast && fast->next)//这部分很简单,找出中间结点 { slow=slow->next; fast=fast->next ->next; } struct ListNode* prev=NULL; struct ListNode* mid=slow; struct ListNode* end=NULL; while(mid)//这部分是逆置,在这走了不少弯路, //如果按照三个指针岔开的方法即NULL,slow,slow->next,很容易出现空指针出错 //这种方法将后两个指针步进一致巧妙避免了这个问题,或者将逆置单独写在函数也可以避免。 { end=mid->next; mid->next=prev; prev=mid; mid=end; } while(head && prev)//比较部分也很简单,逆置后的表头是prev, //因为逆置后的表尾(原中间结点)next被置为NULL, //所以不用关心原表奇数偶数只要出现NULL就可以结束比较 { if(head->val!=prev->val) { return 0; } head=head->next; prev=prev->next; } return 1; }