题目
给你一个单链表的头节点 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());
}
}
