题目描述：
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2输出: false
示例 2:
输入: 1->2->2->1输出: true
思路分析：
迭代法：
避免使用 O(n)O(n) 额外空间的方法就是改变输入。
我们可以将链表的前（后）半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。
该方法虽然可以将空间复杂度降到 O(1)O(1)，但是在并发环境下，该方法也有缺点。在并发环境下，函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执行过程中链表会被修改。
整个流程可以分为以下步骤：
找到前（后）半部分链表的尾节点。
反转（前）后半部分链表。
判断是否回文。
Python实现
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def isPalindrome(self, head): """ :type head: ListNode :rtype: bool """ if head is None or head.next is None: return True if head.next.next is None: return head.val == head.next.val fast = slow = q = head while fast.next and fast.next.next:#这里快指针的判读条件跟判断环形有一点不同 fast = fast.next.next slow = slow.next def reverse_list(head): if head is None: return head cur = head pre = None nxt = cur.next while nxt: cur.next = pre pre = cur cur = nxt nxt = nxt.next cur.next = pre return cur p = reverse_list(slow.next) while p.next: if p.val != q.val: return False p = p.next q = q.next return p.val == q.val
java实现：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) { return true; } ListNode slow=head; ListNode fast=head; ListNode pre=null,prepre=null; //反转前半部分指针 while(fast!=null&&fast.next!=null){ pre=slow; slow=slow.next; fast=fast.next.next; pre.next=prepre; prepre=pre; } if(fast != null) { slow = slow.next; } //比较前后部分指针是否相同 while(pre!=null&&slow!=null){ if(pre.val!=slow.val){ return false; } pre=pre.next; slow=slow.next; } return true; } }
递归法：
currentNode 指针是先到尾节点，由于递归的特性再从后往前进行比较。frontPointer 是递归函数外的指针。若 currentNode.val != frontPointer.val 则返回 false。反之，frontPointer 向前移动并返回 true。
算法的正确性在于递归处理节点的顺序是相反的，而我们在函数外又记录了一个变量，因此从本质上，我们同时在正向和逆向迭代匹配。
所谓递归，即从上往下递下去，然后再从下往上归回来。
java实现代码：
class Solution { private ListNode frontPointer; private boolean recursivelyCheck(ListNode currentNode) { if (currentNode != null) { if (!recursivelyCheck(currentNode.next)) { return false; } if (currentNode.val != frontPointer.val) { return false; } frontPointer = frontPointer.next; } return true; } public boolean isPalindrome(ListNode head) { frontPointer = head; return recursivelyCheck(head); }
