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

问：

给定一个单链表的头节点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;
}