①中文题目
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
。
②思路
首先，找到链表的中间结点在哪，用j标记，此处用到leetcode的876题，也就是我上一篇博文里那个题。从而把链表分为前半截和后半截。
然后，把后半截链表反转一下，记为x，如果x和前半截链表长得一模一样，那就返回true，不一样就返回false。
③代码
1 class Solution { 2 public boolean isPalindrome(ListNode head) { 3 ListNode temp1=head; 4 ListNode temp2=head; 5 int i=1; 6 int k=0; 7 boolean flag=false; 8 while(head==null||head.next==null) 9 return true; //链表长度为0或者1，要单独拿出来说 10 11 12 while(temp1.next!=null){ 13 i+=1; 14 temp1=temp1.next; 15 } 16 for(int j=0;j<i/2;j++){ //i就是链表的一半处 17 temp2=temp2.next; //找到中间结点 18 } //至此，temp2就是后半截链表的头结点 19 ListNode pre=null; 20 ListNode curr; //curr是后半截链表的起点。 21 if(i%2==0) //根据链表长度为奇数还是偶数，来决定后半截链表的起点。 22 curr=temp2; 23 else 24 curr=temp2.next; 25 ListNode buf=null; //buff就是个缓存而已，有点像206题里的temp 26 while(curr!=null){ 27 buf=curr.next; 28 curr.next=pre; 29 pre=curr; 30 curr=buf; //整个反转过程，时间复杂度是O(N)，空间复杂度是O(1) 31 } //至此，后半截链表已经被反转 //head保存的是前半截链表的头结点，pre是后半截链表反转之后的头结点 32 while(pre!=null){ //不能用head.next!=null去判断，因为前半截的最后一个结点的后边不是null。 33 if(head.val==pre.val){ 34 head=head.next; 35 pre=pre.next; 36 k+=1; 37 } 38 else{ 39 return false; //一旦发现元素不等的现象，立刻返回false 40 } 41 } 42 if(k==i/2) 43 flag=true; //用k来作为flag翻不翻转的标志 44 return flag; 45 46 } 47 }
④运行结果
执行结果：通过
显示详情
执行用时 :1 ms, 在所有 Java 提交中击败了99.89%的用户
内存消耗 :40.4 MB, 在所有 Java 提交中击败了97.88%的用户
⑤学到的东西
1、回文链表是什么？
上海自来水来自海上
黄山落叶松叶落山黄。这个例子摘自网上别人的回答。
2、回文链表里，如果链表长度为0,1个，都要单独拿出来讨论。
3、链表长度为奇数和偶数时，后半截链表的起点是不一样的。
比如链表长度为5，比如[1,2,3,2,1]，那么如果后半截链表起点应该是[3,2,1]中的2，而不是3。
比如链表长度为6，比如[1,2,3,3,2,1]，那么如果后半截链表起点应该是[3,2,1]中的3。
4、本题就是206题和876题的结合，我把两个程序并在一起写的。我看到网上有的人是把两个程序写在两个函数里的，再进行调用的。
比如把206题程序装在reverseListNode函数里，把876题装在getMidListNode函数里，再在主程序里调用（不是main函数，就是普通函数之间的调用）。