LinkLists 检查一个链表是否为回文 Check if a linked list is palindrome @CareerCup

Implement a function to check a linked list is a palindrome

检查一个链表是否为回文

思路：

1 Iterative，利用栈，把链表前半段存入栈，再逐个弹栈和链表后半段比较。注意链表长度为奇数的情况！要跳过中间节点！

2 递归！

定义递归函数为Result rec(LinkedListNode head, int length) 意义为传入链表头结点和链表长度，返回该链表的尾节点的下一个节点

Result是一个Wrapper 类，包含了node和当前是否match的判断

递归的关键是要清楚递归函数的每一个参数的意义是什么，还有返回值的意义是什么！！！

如下图：假设在递归的某一个阶段，要比较前半段的那个1和后半段的那个1是否相等：

根据递归可以得到蓝色部分的返回值Result，包含了一个res.node和match值。res.node的意义就是该子链表的尾节点的下一个节点，即后半段的1！

然后我们可以把head指向的1和res.node指向的1比较。如果相同则设置match为true，并且更新本层递归（红色区域）的返回值为本层子链表的尾节点（1）的下一个节点（0），作为res.node返回。

package LinkLists;

import java.util.Stack;

import CtCILibrary.LinkedListNode;

public class S2_7 {

	// 利用栈，把链表前半段存入栈，再逐个弹栈和链表后半段比较
	public static boolean isPalindrome(LinkedListNode head) {
		LinkedListNode fast = head;
		LinkedListNode slow = head;

		Stack<Integer> stack = new Stack<Integer>();

		while (fast != null && fast.next != null) {
			stack.push(slow.data);
			slow = slow.next;
			fast = fast.next.next;
		}

		if (fast != null) { // 只有当链表长度为奇数时，fast才不会为null
			slow = slow.next; // 这时要跳过中间节点
		}

		while (slow != null) { // 边弹栈边比较
			int top = stack.pop().intValue();
			if (top != slow.data) {
				return false;
			}
			slow = slow.next;
		}
		return true;
	}

	// 递归
	public static boolean isPalindrome2(LinkedListNode head) {
		int size = 0;
		LinkedListNode n = head;
		while (n != null) {
			size++;
			n = n.next;
		}
		Result p = rec(head, size);
		return p.match;
	}

	// 传入链表头结点和链表长度，返回该链表的尾节点的下一个节点
	public static Result rec(LinkedListNode head, int length) {
		if (head == null || length == 0) {	// 空链表，肯定是回文
			return new Result(null, true);
		} else if (length == 1) {		// 只有1个节点，肯定是回文
			return new Result(head.next, true);
		} else if (length == 2) {		// 有两个节点，如果相同则是回文
			return new Result(head.next.next, head.data == head.next.data);
		}
		
		Result res = rec(head.next, length-2);		// 长度缩小2的子链表问题，res存放子问题的结果和子链表尾节点的下一个节点
		if(!res.match || res.node==null) {			// 不match
			return res;
		} else{
			res.match = head.data == res.node.data;		// 比较当前节点和尾节点是否相等
			res.node = res.node.next;							// 更新返回值，即该链表的尾节点的下一个节点
			return res;
		}
	}
	
	static class Result {
		public LinkedListNode node;
		public boolean match;
		public Result(LinkedListNode n, boolean res) {
			node = n;
			match = res;
		}
	}
	
	
	public static void main(String[] args) {
		int length = 10;
		LinkedListNode[] nodes = new LinkedListNode[length];
		for (int i = 0; i < length; i++) {
			nodes[i] = new LinkedListNode(i >= length / 2 ? length - i - 1 : i, null, null);
		}

		for (int i = 0; i < length; i++) {
			if (i < length - 1) {
				nodes[i].setNext(nodes[i + 1]);
			}
			if (i > 0) {
				nodes[i].setPrevious(nodes[i - 1]);
			}
		}
//		 nodes[length - 2].data = 9; // Uncomment to ruin palindrome

		LinkedListNode head = nodes[0];
		System.out.println(head.printForward());
		System.out.println(isPalindrome2(head));
	}

}