題目

給你一個單鏈表的頭節點 head ，請你判斷該鏈表是否為回文鏈表
。如果是，返回 true ；否則，返回 false 。
示例 1：
輸入：head = [1,2,2,1]
輸出：true

分析

可以用快慢指針的方式找到鏈表的中間結點，然后再將前半部分鏈表進行翻轉，然后開始比較前半段鏈表和后半段鏈表是否嚴格一致即可

public class LinkNode {int val;LinkNode next;public LinkNode(int data) {this.val = data;this.next = null;}
}
public class LinkList {LinkNode head;public LinkList() {this.head = null;}public LinkNode getHead() {return this.head;}//添加元素public void addNode(int data) {LinkNode node = new LinkNode(data);if (this.head == null) {this.head = node;} else {LinkNode cur = this.head;while(cur.next != null) {cur = cur.next;}cur.next = node;}}//正序打印public void print(LinkNode node) {while(node != null) {System.out.print(node.val);System.out.print(" ");node = node.next;}System.out.println();}public boolean huiwen() {if(this.head == null) {return false;}if(this.head.next == null) {return true;}LinkNode fast = this.head;LinkNode slow = this.head;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}LinkNode pre = null;LinkNode cur = this.head;while(cur != slow) {LinkNode next = cur.next;cur.next = pre;pre = cur;cur = next;}LinkNode last;if(fast == null) {last = slow;} else {last = slow.next;}while(last != null && pre != null) {if(last.val != pre.val) {return false;}last = last.next;pre = pre.next;}if(pre != null || last != null) {return false;}return true;}
}
public class palindromeLinkedList {public static void main(String[] args) {LinkList list = new LinkList();list.addNode(1);list.addNode(2);list.addNode(2);list.addNode(1);System.out.println(list.huiwen());list = new LinkList();list.addNode(1);list.addNode(2);list.addNode(4);list.addNode(2);list.addNode(1);System.out.println(list.huiwen());list = new LinkList();list.addNode(1);list.addNode(3);list.addNode(4);list.addNode(2);list.addNode(1);System.out.println(list.huiwen());}
}