请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
思路: 递归双指针
利用递归自带的栈,实现从链表最后一个元素跳到前一个元素.
(整体: 第一个元素和最后一个元素比较,第二个元素和倒数第二个元素比较...)
思路2: 快慢指针 - 但是我觉得递归更舒服 orz
1 class Solution234 {
2
3 private ListNode currNode;
4
5 public boolean isPalindrome(ListNode head) {
6 currNode = head;
7 return compare(head);
8 }
9
10 private boolean compare(ListNode head) {
11 if (head == null || head.next == currNode || (head.next != null) && (head.next.next== currNode)) { //比较n/2次,但递归结束条件过多反而会影响效率(和只带一个结束条件比较n次的递归效率差不多)
13 return true;
14 }
15 boolean nextRes = compare(head.next);
16 ListNode temp = currNode;
17 currNode = currNode.next;
18 return temp.val == head.val && nextRes;
19 }
20 }
原文：https://www.cnblogs.com/rainbow-/p/10587564.html