题目

回文结构是指从中间节点的两边对称. 如 1→2-3→2→1.

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

解答

先使用双指针, 将链表从中间节点分为两部分.

将右边链表插入到栈中.

从链表头部, 即左边链表的头部开始遍历. 如果与栈顶元素不一致, 则不是回文结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


public boolean isPalindrome(Node head) {
		if (head == null || head.next == null) {
			return true;
		}
		// 找到右边部分的开始节点
		Node temp = head, right = head.next;
		while (temp.next != null && temp.next.next != null) {
			temp = temp.next.next;
			right = right.next;
		}
		// 将右边部分写入栈中
		Stack<Node> stack = new Stack<>();
		while (right != null) {
			stack.push(right);
			right = right.next;
		}
		// 对比左边部分与右边部分
		while (!stack.isEmpty()) {
			if (head.value != stack.pop().value) {
				return false;
			}
			head = head.next;
		}
		return true;
	}

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

题目

解答