第二章 链表问题（判断一个链表是否为回文）

【题目】

        给定一个链表的头节点head,请判断该链表是否为回文结构。如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。

例如:

1->2->1，返回true

1->2->2->1，返回true

15->6->15，返回true

1->2->3，返回false

【解答】

第一种解法

    boolean isPalindrome(Node<Integer> head) {// 将链表的后半段放入栈中，压入完成后，再检查栈顶到栈底值出现的顺序是否和链表左半部分的值相对应if (head == null || head.next == null) {return true;}// 通过快慢指针找到链表的后半段Node<Integer> right = head.next;Node<Integer> fast = head;while (right.next != null && right.next.next != null) {right = right.next;fast = fast.next.next;}Stack<Integer> stack = new Stack<Integer>();while (right != null) {stack.push(right.value);right = right.next;}Node<Integer> temp = head;while (!stack.isEmpty()) {if (!stack.pop().equals(temp.value)) {return false;} else {temp = temp.next;}}return true;}

第二种解法

 public static boolean method01(Node<Integer> head) {Node<Integer> n1 = head;Node<Integer> n2 = head;while (n1.next != null && n2.next.next != null) { // 查找中间节点n1 = n1.next; // 中部n2 = n2.next.next; //结尾}n2 = n1.next; // 右半部分的起始节点n1.next = null; // mid.next -> nullNode<Integer> n3 = null;while (n2 != null) { // 右半区反转n3 = n2.next; // n3 -> 保存下一节点n2.next = n1; // 下一个反转节点n1 = n2; // n1 移动n2 = n3; // n2 移动}n3 = n1; // n3 -> 保存最后一个节点n2 = head; // n2 -> 左边第一个节点boolean res = true;while (n1 != null && n2 != null) { //检查回文if (!n1.value.equals(n2.value)) {res = false;break;}n1 = n1.next; // 从右到中部n2 = n2.next; // 从左到中部}n1 = n3.next;n3.next = null;while (n1 != null) { // 恢复列表n2 = n1.next;n1.next = n3;n3 = n1;n1 = n2;}return res;}