链表中的回文判断

给一个链表，判断这个链表是否为回文链表。能否使用O(1)的空间复杂度解决问题？

思路1：使用辅助空间，我们这里给出了使用动态数组作为检查表，给出了两种实现方式，但是这种实现方式效率不高。

​ public class ListNode { public int val; public ListNode next; public ListNode(int x) { this.val = x; this.next = null; } public static ListNode createList(int[] nums) { if(null == nums || 0 == nums.length) return null; ListNode head = new ListNode(nums[0]); ListNode needle = head; for(int i = 1; i < nums.length;++i) { ListNode node = new ListNode(nums[i]); needle.next = node; needle = needle.next; needle.next = null; } return head; } }

import java.util.ArrayList; import java.util.List; class Solution { public boolean isPalindrome(ListNode head) { if (null == head || null == head.next) return true; List<Integer> all = new ArrayList<Integer>(); while (head != null) { all.add(head.val); head = head.next; } for (int i = 0; i < all.size() / 2; ++i) { if ((int) all.get(i) != (int) all.get(all.size() - 1 - i)) return false; } return true; } public static void main(String[] args) { int[] nums1 = { 1, 2, 4, 2, 1 }; ListNode l1 = ListNode.createList(nums1); boolean result = new Solution().isPalindrome(l1); System.out.print(result); } }

思路2：使用O(1)空间复杂度，即需要的临时空间较少，且跟链表长度没有关系，我们这里给出了两种实现方式，实现思路相同。使用快慢指针，找到中间结点位置，一种是反转链表的前半部分；一种是反转链表的后半部分，反转后半部分更容易实现，效率也要高。

class Solution { public boolean isPalindrome(ListNode head) { if (null == head || null == head.next) return true; // 找中间位置开始 ListNode fast = head; ListNode faster = head; while (faster != null && faster.next != null) { fast = fast.next; faster = faster.next.next; } // 找中间位置结束 // 反转fast之前的所有元素 // pre指向当前结点的前驱，反转后第一个结点的后继 ListNode pre = null; // 指向当前遍历的结点 ListNode cur = head; while (cur != fast) { // 记录当前结点的下一个结点，否则执行下一条一句就丢了后面没有反转的剩余结点 ListNode next = cur.next; // 真正的反转，指针变化方向，因为链表最后一个结点的next为空，这也是为什么pre的初始值为null cur.next = pre; // 向后继续遍历剩余未反转的结点，pre和cur均要向后移动一位 pre = cur; cur = next; } // 到此，cur指向fast，而pre指向了最后一个被反转的结点，也就是新链表的头 // 比较元素值是否相同开始 // 链表元素个数为奇数个的情况 if (null != faster && null == faster.next)// odd fast = fast.next; // 比较反转后的[pre,fast)与[fast,tail]到链表尾部 while (pre != null && fast != null) { if (pre.val != fast.val) return false; pre = pre.next; fast = fast.next; } // 比较元素值是否相同结束 return true; } public static void main(String[] args) { int[] nums1 = { 1, 2, 4, 2, 1 }; ListNode l1 = ListNode.createList(nums1); boolean result = new Solution().isPalindrome(l1); System.out.print(result); } }