leetcode第234题，回文链表。采用双指针+迭代的算法来完成。

LeetCode 234回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

1输入：head = [1,2,2,1]
2输出：true

示例 2：

1输入：head = [1,2]
2输出：false

提示：

  • 链表中节点数目在范围[1, 105] 内
  • 0 <= Node.val <= 9

**进阶：**你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路

可以直接构建一个数组来存放这些元素，但不满足空间复杂度o(1)的要求

还是采用双指针的方式，但是还是有区别。

  1. 根据回文链表特性，前后半部分是对称的，所以后半部分可以做链表反转，如题目LeetCode 206的反转链表一样
  2. 引入快慢双指针，慢指针每次移动一个单位，快指针每次移动两个单位，如果快指针当前或者快指针的后面一个元素为null，那么记录下慢指针当前的位置。
  3. 判断奇偶性，快指针不为null，那么链表长度是奇数，慢指针往后移动一位，快指针为null，那么链表长度为偶数，慢指针不操作。
  4. 反转慢指针当前位置到链表尾部的结点，并将快指针移动到链表首部，同时快慢指针遍历元素，且快慢指针每次移动一个单位，直到慢指针指向链表尾部找不到和快指针不相同的元素，那么该链表为回文链表。
 1/**
 2 * Definition for singly-linked list.
 3 * public class ListNode {
 4 *     int val;
 5 *     ListNode next;
 6 *     ListNode() {}
 7 *     ListNode(int val) { this.val = val; }
 8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9 * }
10 */
11class Solution {
12    public boolean isPalindrome(ListNode head) {
13        if(null == head) return false;
14
15        ListNode fast = head;
16        ListNode slow = head;
17
18        while(null != fast && null != fast.next)
19        {
20            fast = fast.next.next;
21            slow = slow.next;
22        }
23        //说明是奇数链表
24        if(null != fast)
25        {
26            slow = slow.next;//移动慢指针
27        }
28
29        fast = head;
30        slow = reverseList(slow);
31
32        while(null != slow)
33        {
34            if(fast.val != slow.val)
35            {
36                return false;
37            }
38
39            fast = fast.next;
40            slow = slow.next;
41        }
42        return true;
43
44    }
45
46    //反转链表不要使用递归，会创建大量的临时变量和遍历
47    public ListNode reverseList(ListNode head) {
48        if(null == head) return null;
49        ListNode preNode = null;//保存每一个链表结点的值
50        //ListNode cur = head;//链表的当前指向结点
51        while(null != head)
52        {
53            ListNode next = head.next;
54            head.next = preNode;
55            preNode = head;
56            head = next;
57        }
58        return preNode;
59    }
60}