[程序员面试代码指南]链表问题-判断一个链表是否是回文结构(链表)

题目

如题

题解

步骤

1 找到链表中点，
2 翻转右半部分，
3 断开两侧，从两个链表头开始判断节点值相同。
4 然后再将右侧链表翻转回来

复杂度

时间O(n) 空间O(1)

代码

//public class Node{
//	int val;
//	Node next;
//	Node(int val){
//		this.val=val;
//	}
//}
public class Main {
	public static void main(String[] args) {
		Node n1=new Node(1);
		Node n2=new Node(2);
		Node n3=new Node(3);
		Node n4=new Node(3);
		Node n5=new Node(2);
		Node n6=new Node(1);
		
		n1.next=n2;
		n2.next=n3;
		n3.next=n4;
		n4.next=n5;
		n5.next=n6;
		Node head=n1;
		
		boolean ans=palindromeTree(head);
		System.out.println(ans);
	}
	
	public static boolean palindromeTree(Node head){
		//找到中点
		Node mid=head;//中点
		Node fast=head;
		while(fast.next!=null&&fast.next.next!=null) {//奇偶长度情况
			fast=fast.next.next;
			mid=mid.next;
		}
		
		//翻转右侧链表
		Node cur=mid.next;//
		mid.next=null;
		Node behind=null;
		Node before=null;
		while(cur!=null) {
			behind=cur.next;
			cur.next=before;
			before=cur;
			cur=behind;
		}
		Node rHead=before;
		
		//检查是否是回文的
		Node lNode=head;
		Node rNode=before;//
		boolean res=true;
		while(lNode!=null&&rNode!=null) {//原链奇偶长度都ok
			if(lNode.val!=rNode.val) {
				res=false;
				break;
			}
			lNode=lNode.next;
			rNode=rNode.next;
		}
		
		//右侧链表翻转回去
		before=rHead;
		cur=rHead.next;
		behind=null;
		while(cur!=null) {
			behind=cur.next;
			cur.next=before;
			before=cur;
			cur=behind;
		}
		
		return res;
	}
}