11.2

判断一个链表是否为回文结构

给定一个链表的头节点head，请判断该链表是不是回文结构。
例如：
1->2->1，返回true。
1->2->2->1，返回true。
15->6->15，返回true。
1->2->3，返回false。

思路 & 代码

//链表结构
public static class Node {
	public int value;
	public Node next;

	public Node(int data) {
		this.value = data;
	}
}

空间复杂度O(n/2)

使用2个指针，一个快一个慢，快的一次走2步，慢的一次走一步，直到空为止
此时慢指针停在中间位置，然后将慢指针后面的内容入栈
因为栈是逆序的，所以相当于将后半部分的链表逆序
然后从栈顶与链表头开始比较是否相同
当元素个数为奇数时，如1,2,3,2,1，入栈的值为3,2,1
当元素个数为偶数时，如1,2,3,4,2,1，入栈的值为4,2,1

public static boolean isPalindrome1(Node head) {
	if(head == null || head.next == null){
		//链表为空或者只有一个元素
		return true;
	}
	//慢指针
	Node ns = head;
	//快指针
	Node nq = head;
	//这里判断的条件不是nq.next.next
	//因为可能nq到了末尾，而nq.next为空，nq.next.next是不存在的
	//也可能是nq为被赋值为空
	while(nq != null && nq.next != null){
		//快指针一次走2步，慢指针一次走一步
		ns = ns.next;
		nq = nq.next.next;
	}
	Stack<Node> stack = new Stack<Node>();
	//慢指针的后半段入栈
	while(ns != null){
		stack.push(ns);
		ns = ns.next;
	}
	
	//栈中内容与链表头开始比较
	while(!stack.empty()){
		if(head.value != stack.pop().value){
			//元素不符合
			return false;
		}
		head = head.next;
	}
	
	return true;
}

空间复杂度O(1)

该方法改变了链接的结构，之后要进行还原
这个方法与前一种部分类似，也是在快慢指针一起走直到为空。
之后就有所区别了，即将慢指针后半部分的值全部反向指

• 原链表为1,2,3,2,1，修改后为1->2->3<-2<-1
• 原链表为1,2,3,4,2,1，修改后为1->2->3->4<-2<-1

然后从两端分别遍历，查看是否是回文
注意的是节点为空的情况

//只用空间复杂度O(1)
public static boolean isPalindrome2(Node head) {
	boolean res = true;
	if(head == null || head.next == null){
		//链表为空或者只有一个元素
		return true;
	}
	//慢指针
	Node ns = head;
	//快指针
	Node nq = head;	
	while(nq != null && nq.next != null){
		ns = ns.next;
		nq = nq.next.next;
	}

	
	//将ns后面的链表反转
	Node prior = ns;
	Node cur = ns.next;
	//两个节点单独判断
	if(cur == null){
		//说明此链表中只有2个元素,直接返回不需要修复
		return head.value == ns.value ? true: false;
	}
	//只有两个节点的时候，无nextNode
	Node nextNode = cur.next;
	//将中间的节点的后继设为空
	ns.next = null;
	while(cur != null) {
		//反向指
		cur.next = prior;
		prior = cur;
		cur = nextNode;
		//判空,因为cur为空，nextNode不存在
		if(cur == null){
			break;
		}
		nextNode = nextNode.next;
	} 
	
	//结束后prior就是头结点
	//head和prior不能破坏因为还要修复链表
	ns = head;
	cur = prior;
	//判断是否是回文
	while(ns != null && cur != null){
		if(ns.value != cur.value){
			res = false;
		}
		ns = ns.next;
		cur = cur.next;
	}
	

	//修复链表
	cur = prior.next;
	//nextNode可能为空，当只有3个元素的时候，所以下面重置nextNode会判断
	nextNode = cur.next;
	prior.next = null;
	while(cur != null){
		cur.next = prior;
		prior = cur;
		cur = nextNode;
		//判空,因为cur为空，nextNode不存在
		if(cur == null){
			break;
		}
		nextNode = nextNode.next;
	}
	return res;
	
}