判断一个链表是否为回文结构
《程序员代码面试指南》第18题 P55 难度:士★☆☆☆(普通解法)| 尉★★☆☆(进阶解法)
普通解法很简单,我也秒想出来,用栈来解决。
书上有两种方法,一是将整个链表压入栈,然后再从头遍历,每个节点与弹出的栈顶作比较;
另一种方法是将链表的右半部分压入栈中,然后再从左半部分头结点开逐一始与弹出的栈顶作比较。
对于书上的方法2我有点不理解为什么要多此一举。我的方法是:
将链表的左半部分依次压入栈中,然后从右半部分第一个节点开始,逐一与弹出的栈顶作比较;
全部相等,则是回文结构;否则不是。这样的话只需要从头开始遍历一次。
(不过可能是因为书上方法2的前提条件是事先不知道总节点数)
进阶解法的思路是,将右半部分节点反转,然后2个指针分别从头结点和尾结点向中间移动。如果节点值有不相等的就不是回文结构。
需要注意,判断完后还需要将链表恢复原样。(我一开始以为就算这样还是破坏过链表,就否定了这个方法,没想到还真是这样去做(⊙o⊙)…)
普通与进阶解法的题解代码如下:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
/**
* @描述:判断一个链表是否为回文结构
* @思路:具有两种解法
* @链接:https://www.nowcoder.com/practice/4b13dff86de64f84ac284e31067b86e2
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String n = in.readLine();
String[] items = in.readLine().split(" ");
Node head = Node.createNodeList(items);
System.out.println(IsPalindrom.isPalindrom(head));
}
}
class IsPalindrom {
/**
* 基础解法:
* 1. 将链表的右半区入栈
* 2.检查栈中的值和顺序是否与未入栈的一致
*
* @复杂度:时间O(N) 空间O(N)
*/
public static boolean isPalindrom(Node head) {
//检验
if (head == null || head.getNext() == null) {
return false;
}
//--找到右半区的头结点
Node right = head.getNext(); //从第二个结点开始
Node last = head;
while (last.getNext() != null && last.getNext().getNext() != null) {
right = right.getNext(); // right ->中部
last = last.getNext().getNext(); //cur-->尾部
}
//--将链表的右半区入栈
Stack<Integer> stack = new Stack<Integer>();
while (right != null) {
stack.push(right.getValue());
right = right.getNext();
}
//--检查栈中的值和顺序是否与未入栈的一致
Node node = head;
while (!stack.isEmpty()) {
if (stack.pop() != node.getValue()) {
return false;
}
node = node.getNext();
}
return true;
}
/**
* 进阶解法:时间O(n),空间O(1)
* 举例: 1 -> 2 -> 3 -> 4 -> 5
* 1.改变链表右半区结构:令反转右半区,最后指向链表中间的节点;
* 即:1 -> 2 -> 3 <- 4 <- 5
* 2.leftStart和rightStart同时向中间移动,比较相应结点的值,看是否满足回文结构;
* 3.无论结果如何,都应该将链表恢复成原来的样子,然后在返回检查结果;
*/
public boolean isPalindrome1(Node head) {
//校验
if (head == null || head.next == null) {
return false;
}
//找到中间节点,循环结果:n1->中间节点; n2->结尾
Node n1 = head;
Node n2 = head;
while (n2.next != null && n2.next.next != null) {
n1 = n1.next;
n2 = n2.next.next;
}
//反转右半区,循环结果: n1->最后节点; n2、n3->null
n2 = n1.next; //右半区的头节点
n1.next = null; //令mid节点 -> null
Node n3;
while (n2 != null) {
n3 = n2.next;
n2.next = n1;
n1 = n2;
n2 = n3;
}
//比较左右半区的值来检查是否符合回文结构,获得结果
n2 = head;
n3 = n1;
boolean res = true;
while (n1 != null && n2 != null) {
if (n1.value != n2.value) {
res = false;
break;
}
n1 = n1.next;
n2 = n2.next;
}
//恢复链表原本的结构
n2 = n3.next;
n3.next = null;
while (n2 != null) {
n1 = n2.next;
n2.next = n3;
n3 = n2;
n2 = n1;
}
return res;
}
public static void main(String[] args) {
Node head = Node.createNodeList(new Integer[]{1, 2, 3, 2, 5});
System.out.println(IsPalindrom.isPalindrom(head));
}
}
class Node {
public Node next;
public int value;
public Node(int value) {
this.value = value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public static Node createNodeList(Integer[] values) {
Node head = new Node((values[0]));
Node node = head;
for (int i = 1; i < values.length; i++) {
Node newNode = new Node(values[i]);
node.next = newNode;
node = newNode;
}
return head;
}
public static Node createLoopNodeList(Integer[] values) {
Node head = new Node((values[0]));
Node node = head;
for (int i = 1; i < values.length; i++) {
Node newNode = new Node(values[i]);
node.next = newNode;
node = newNode;
}
node.setNext(head);
return head;
}
public static Node createNodeList(String[] values) {
Node head = new Node(Integer.parseInt(values[0]));
Node node = head;
for (int i = 1; i < values.length; i++) {
Node newNode = new Node(Integer.parseInt(values[i]));
node.next = newNode;
node = newNode;
}
return head;
}
public static void printNodeList(Node head) {
StringBuilder sb = new StringBuilder();
while (head != null) {
sb.append(head.getValue()).append(" ");
head = head.getNext();
}
System.out.println(sb.toString());
}
public static void printLoopNodeList(Node head) {
if (head == head.getNext()) { //只有一个节点
System.out.println(head.getValue());
} else {
StringBuilder sb = new StringBuilder();
Node last = head;
while (last.getNext() != head) {
sb.append(last.getValue()).append(" ");
last = last.getNext();
}
System.out.println(sb.toString());
}
}
}
需要学习一下这个确定中间节点的方法(事先不知道总节点数),两个节点每次分别移动1和2个,当移动2个的节点移动到最后时,另一个节点就正好移动到了中间。