题目

给定一个链表的头节点head，请判断该链表是否为回 文结构。
例如: 1->2->1，返回true。
1->2->2->1，返回true。
15->6->15，返回true。
1->2->3，返回false。
进阶：
如果链表长度为N，时间复杂度达到O(N)，额外空间复杂 度达到O(1)。

链表结构如下

  public static class Node {
    public Node next;
    public int value;

    public Node(int data) {
      value = data;
    }
  }

1、基础版--空间复杂度O(N)

思路：

使用栈，将链表的所有数据入栈。然后链表从头开始遍历，每次指针指向下一个节点时，栈弹出，判断两者是否相等，直至栈空都相等的话，那么就是回文链表。

代码实现

public static boolean isPalindromeList1(Node head) {
    Stack<Node> stack = new Stack<Node>();
    Node p = head;
    while(p != null) {
      stack.push(p);
      p = p.next;
    }
    while(head != null) {
      Node node = stack.pop();
      if (node.value != head.value) {
        return false;
      }
      head = head.next;
    }
    return true;
  }

2、进阶版1--空间复杂度O(N/2)

思路

回顾上面的解法，其实我们只需比较到链表的中点即可。因此，我们不再对链表全部入栈，而是先找到链表的中点，然后从中点开始入栈。最后只需比较链表~中点之间的数据和链表是否一一相等即可

算法实现

  public static boolean isPalindromeList2(Node head) {
    Node right = head.next;
    Node cur = head.next.next;
    // 找到中点节点
    while(cur.next != null && cur.next.next != null) {
      right = right.next;
      cur = cur.next.next;
    }
    // 从中间回文开始的节点入栈
    Stack<Node> stack = new Stack<Node>();
    while(right != null) {
      System.out.println(right.value);
      stack.push(right);
      right = right.next;
    }
    // 比较前回文和后回文部分
    while(!stack.isEmpty()) {
      Node node = stack.pop();
      if (node.value != head.value) {
        return false;
      }
      head = head.next;
    }
    return true;
  }

这里需要提到中点链表的查找方法：
1、准备一个慢指针，一次走1格
2、准备一个快指针，一次走2格
3、当快指针走完了，那么慢指针所指向的节点就是中点节点。若不理解，自己画图理解理解

3、进阶版2--空间复杂度O(1)

思路

修改链表的指向，将回文部分链表逆转指向中点，例如：
1 -> 2 -> 3 -> 2 -> 1改为
1 -> 2 -> 3 <- 2 <- 1 这种结构判断
因此，算法步骤如下：
1、我们需要先找到中点节点，然后修改尾节点~中点节点的指向，翻转节点
2、首尾指针开始遍历链表，直至首尾的指针抵达中点，期间判断首尾指针指向的value是否相等
3、还原链表原来的结构（如果要求不能修改链表结构的话，就需要做这步骤，算是可选步骤吧）

算法实现

  public static boolean isPalindromeList3(Node head) {
    Node right = head.next;
    Node cur = head.next.next;
    // 找到中间节点
    while(cur.next != null && cur.next.next != null) {
      right = right.next;
      cur = cur.next.next;
    }
    // 右边第一个节点
    Node n1 = right.next;
    // 使中间节点指向null
    right.next = null;
    Node pre = null;
    Node next = null;
    // 以中间开始，翻转节点
    while(n1 != null) {
      next = n1.next;
      n1.next = pre;
      pre = n1;
      n1 = next;
    }
    // 右边部分的head节点
    Node rightHead = pre;
    Node leftHead = head;
    // 备份最后的指针
    Node lastNode = pre;
    boolean res = true;
    while(leftHead != null && rightHead != null) {
      if(leftHead.value != rightHead.value) {
        res = false;
        break;
      }
      leftHead = leftHead.next;
      rightHead = rightHead.next;
    }
    // 恢复原来的链表结构，可选步骤
    n1 = lastNode;
    pre = null;
    next = null;
    while(n1 != null) {
      next = n1.next;
      n1.next = pre;
      pre = n1;
      n1 = next;
    }
    // 将中间节点重新指向翻转后的最后节点
    right.next = pre;
    return res;
  }