【算法】判断一个链表是否为回文结构

问：

给定一个单链表的头节点head，请判断该链表是否为回文结构

例：

1 -> 2 -> 1返回true；1 -> 2 -> 2 -> 1返回true；15 -> 6 -> 15返回true

答：

笔试：初始化一个栈用来存放链表中右半部分的元素（快慢指针），弹栈的顺序是链表的逆序

public static class Node {
  public int value;
  public Node next;
  
  public Node(int data) {
    this.value = data;
  }
}

//额外空间n
public static boolean isPalindrome1 (Node head) {
  if (head == null || head.next == null) {
    return true;
  }
  Stack<Node> satck = new Stack<Node>();
  //为栈赋值做准备
  Node cur = head;
  //将链表的数据赋到栈中
  while (cur != null) {
    stack.push(cur);
    cur = cur.next;
  }
  //比较栈中的数据与链表中的数据
  while (head != null) {
    if (head.value != stack.pop().value) {
      return false;
    }
    head = head.next;
  }
  return true;
}

//额外空间n/2，快慢指针
public static boolean isPalindrome2 (Node head) {
  if (head == null || head.next == null) {
    return true;
  }
  Node slow = head.next;
  Node fast = head;
  while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  Stack<Node> stack = new Stack<Node>();
  //把后半段链表赋值到栈中
  while (slow != null) {
    stack.push(slow);
    slow = slow.next;
  }
  //将弹栈元素与前半段链表中元素对比
  while (!stack.isEmpty()) {
    if (head.value != stack.pop().value) {
      return false;
    }
    head = head.next;
  }
  return true;
}

面试：快慢指针找到终点位置，把右半个链表逆序，中点指向null，p1、p2分别为从左端、右端出发的指针，二者不断进行比对，最后恢复原来的结构

//额外空间1
public static boolean isPalindrome3 (Node head) {
  if (head == null || head.next == null) {
    return true;
  }
  //找到链表中点
  Node slow = head;
  Node fast = head;
  while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  //反转链表的后半段
  fast = slow.next;
  slow.next = null;
  Node n = null;
  while (fast != null) {
    n = fast.next;
    fast.next = slow;
    slow = fast;
    fast = n;
  }
  //将前半段与后半段比较
  n = slow;
  fast = head;
  boolean res = true;
  while (slow != null && fast != null) {
    if (slow.value != fast.value) {
      res = false;
      break;
    }
    slow = slow.next;
    fast = fast.next;
  }
  //把链表恢复原样
  slow = n.next;
  n.next = null;
  while (slow != null) {
    fast = slow.next;
    slow.next = n;
    n = slow;
    slow = fast;
  }
  return res;
}