题目描述（简单难度）

判断一个链表存储的数字是否是回文数字。

思路分析

这个题就难在链表不能随机读取，不能像数组那样直接首尾首尾的依次判断。如果不考虑额外的空间的话，我们只需要把链表中的数字存储到数组中然后判断即可。

如果不用额外空间的话，我们可以把链表分成两半，把后一半倒置，和前一半依次判断即可。

解法一

两个关键点。

• 链表分成两半。

  最直接的方法就是先遍历一遍链表得到链表的长度 n，然后再遍历 n/2 次就找到了中点。

  还有一个比较 trick 的方法，在 143 题，148 题 都用过了，也就是快慢指针，快指针一次走两步，慢指针一次走一步，当快指针走到终点的时候，慢指针此时就到了中点。

  // 找中点，链表分成两个 ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } 

  需要注意的是，当链表个数为偶数的时候，slow 指向第二个链表的开始。当链表个数为奇数的时候是，slow 指向最中间的位置。

• 链表倒置

  在 第 2 题 的时候已经介绍过链表倒置了。

  private ListNode reverseList(ListNode head) { if (head == null) { return null; } ListNode tail = null; while (head != null) { ListNode temp = head.next; head.next = tail; tail = head; head = temp; } return tail; } 

然后整体的代码就出来了。

public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } // 找中点，链表分成两个 ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } // 第二个链表倒置 ListNode newHead = reverseList(slow); // 前一半和后一半依次比较 while (newHead != null) { if (head.val != newHead.val) { return false; } head = head.next; newHead = newHead.next; } return true; } private ListNode reverseList(ListNode head) { if (head == null) { return null; } ListNode tail = null; while (head != null) { ListNode temp = head.next; head.next = tail; tail = head; head = temp; } return tail; } 

总

其实还有一个争议的地方，利用输入的数据，算不算空间复杂度是 O(1)，上边的解法我们改变了原来链表的结构，即使我们在 return 前可以再将链表还原，但如果较真的话，还是可以说它空间复杂度不是 O(1)，因为如果输入的数据只是可读的，我们的算法确实需要额外空间。

详见 discuss-space") 里大神们的讨论，我觉得不用纠结，因为这完全取决于定义，定义的话不也是人定的吗，达成共识即可，具体问题再具体分析。