准备工作:
class Node {
public int value;
public Node next;
public Node(int value) {
this.value = value;
}
}
//创建一个单链表类方便管理单链表
class NodeList {
public Node first;
//统计单链表中元素个数
public int count = 1;
//此处只给了一个含参构造方法,要求创建一个单链表的时候给出头
public NodeList(Node first) {
this.first = first;
}
public void add(Node node) {
Node tmp = first;
while (tmp.next != null) {
tmp = tmp.next;
}
count++;
tmp.next = node;
}
}
搞个链表:
public class Test {
public static void main(String[] args) {
//创建单链表并且添加元素
NodeList nodeList = new NodeList(new Node(1));
nodeList.add(new Node(2));
nodeList.add(new Node(3));
nodeList.add(new Node(2));
nodeList.add(new Node(1));
//判断是否回文
System.out.println(isPlalindrome不考虑(nodeList));
System.out.println(isPlalindrome考虑(nodeList));
}
}
正式操作
一:在不考虑空间复杂度的情况下
将其压入栈中,根据栈后入先出的特点完成判断
?
/**
* 在不考虑空间复杂度的时候
* 将链表中元素依次加入栈中
* 然后从栈中后半截依次弹出,将其与链表中的元素依次比较
*/
public static boolean isPlalindrome不考虑(NodeList nodeList) {
Stack<Node> stack = new Stack<>();
Node tmp = nodeList.first;
while (tmp != null) {
stack.push(tmp);
tmp = tmp.next;
}
Node tmp1 = nodeList.first;
int i = stack.size()/2;
while (i != 0) {
if (stack.pop().value != tmp1.value) {
return false;
}
tmp1 = tmp1.next;
i--;
}
return true;
}
二:在空间复杂度尽可能低的情况下
public static boolean isPlalindrome考虑(NodeList nodeList) {
if (nodeList.count == 1) {
return true;
}
if (nodeList.count == 2) {
if (nodeList.first.value == nodeList.first.next.value) {
return true;
} else {
return false;
}
}
Node p1 = nodeList.first;
Node p2 = nodeList.first;
Node tmp = null;
//如果是偶数个
if (nodeList.count % 2 == 0) {
//使得p1在最后指向前半截最后一个,p2指向最后一个
p2 = p2.next;
while (p2.next != null) {
p2 = p2.next.next;
p1 = p1.next;
}
p2 = p1;
while (p1.next == null) {
tmp = p1.next.next;
p1.next = p1;
p1 = tmp;
}
}
//如果是奇数个
if (nodeList.count % 2 == 1) {
//使p1指向中间,p2指向最后一个
while (p2.next != null) {
p2 = p2.next.next;
p1 = p1.next;
}
}
reverse(p1);
//将p1指向最开始
p1 = nodeList.first;
while (p2.next != null) {
if (p2.value != p1.value) {
return false;
}
p1 = p1.next;
p2 = p2.next;
}
return true;
}
//传入单链表中的一个节点,使得该节点后所有的节点反向指向,而该节点指向null,
public static void reverse(Node nodeFirst) {
if (nodeFirst == null || nodeFirst.next == null) {
return;
}
Node p1 = nodeFirst;
Node p2 = nodeFirst.next;
nodeFirst.next = null;
Node tmp = null;
while (p2 != null) {
tmp = p2.next;
p2.next = p1;
p1 = p2;
p2 = tmp;
}
}
如果觉得文章对你有用,别忘了点赞哦~
|