这里新题，回文链表回文链表链接：https://leetcode-cn.com/problems/palindrome-linked-list/请判断一个链表是否为回文链表。例子一：输入：1->2输出：false例子二：输入：1->2->2->1输出：true思路数组模拟最直接的思路就是把链表打包成数组，然后判断是否返回艺术。代码也比较简单。如下：classSolution{public:boolisPalindrome(ListNode*head){vectorvec;ListNode*cur=head;while(cur){vec.push_back(cur->val);cur=cur->next;}//比较数组回文for(inti=0,j=vec.size()-1;inext;}vectorvec(length,0);//给定vector的初始长度，以免每隔一段时间重新开辟空间timethevector添加节点cur=head;intindex=0;while(cur){vec[index++]=cur->val;cur=cur->next;}//比较数组回文for(inti=0,j=vec.size()-1;inext==nullptr)重新turntrue;ListNode*slow=head;//慢指针，找到链表的中间位置，作为拆分ListNode*fast=head;ListNode*pre=head;//记录慢指针的前一个节点，用于拆分链表while(fast&&fast->next){pre=slow;slow=slow->next;fast=fast->next->next;}pre->next=nullptr;//拆分链表ListNode*cur1=head;//前半部分ListNode*cur2=reverseList(slow);//反转后半部分，如果链表总长度为奇数，则cur2比cur1多一个节点//开始两个链表的比较while(cur1){if(cur1->val!=cur2->val)returnfalse;cur1=cur1->next;cur2=cur2->next;}returntrue;}//反向链表ListNode*reverseList(ListNode*head){ListNode*temp;//保存cur的下一个节点ListNode*cur=head;ListNode*pre=nullptr;while(cur){temp=cur->next;//保存cur的下一个节点，因为cur->nextcur->next=pre会被next改变;//翻转操作//更新pre和cur指针pre=cur;cur=temp;}returnpre;}};其他语言版本Java//方法一，使用数组classSolution{publicbooleanisPalindrome(ListNodehead){intlen=0;//统计链表长度ListNodecur=head;while(cur!=null){len++;cur=cur.next;}cur=head;int[]res=newint[len];//向数组中添加元素for(inti=0;ibool:length=0tmp=headwhittmp:#链表长度length+=1tmp=tmp.nextresult=[0]*lengthtmp=headindex=0whileetmp:#链表元素加入数组result[index]=tmp.valindex+=1tmp=tmp.nexti,j=0,length-1whileibool:ifhead==Noneorhead.next==None:returnTrueslow,fast=head,headwhilefastandfast.next:pre=slowslow=slow.nextfast=fast.next.nextpre.next=None#Splitlinkedlistcur1=head#Firsthalfcur2=self.reverseList(slow)#反转后半段，如果总链表长度为奇数，则cur2比cur1多一个节点whilecur1:ifcur1.val!=cur2.val:returnFalsecur1=cur1.nextcur2=cur2.nextreturnTruedefreverseList(self,head:ListNode)->ListNode:cur=headpre=Nonewhile(cur!=None):temp=cur.next#保存cur的下一个节点cur.next=pre#reversepre=curcur=tempreturnpre
