Java确定单链列表是否是回文
在此程序中，我们需要检查给定的单链列表是否为回文。回文列表就是与之相反的列表。
上图中给出的列表为回文，因为它等效于其反向列表，即，1、2、3、2、1。要检查列表是否是回文，我们遍历该列表并检查开头一半的任何元素与结尾一半的任何元素都不匹配，然后设置变量
最后，如果该标志为假，则列表为回文，否则为非。下面给出检查列表是否为回文的算法:
算法
创建一个具有两个属性的类Node: data和next。下一个是指向列表中下一个节点的指针。
创建另一个具有三个属性的回文类: 头，尾和大小。
addNode()将一个新节点添加到列表中: 创建一个新节点。 首先检查head是否等于null，这意味着列表为空。 如果列表为空，头和尾都将指向新添加的节点。 如果列表不为空，则新节点将被添加到列表的末尾，以使尾部的下一个指向新添加的节点。这个新节点将成为列表的新尾巴。
a.reverseList()将颠倒列表中存在的节点的顺序:
当前节点将表示需要从其反向列表的节点。
节点prevNode代表当前节点的前一个节点，nextNode代表当前节点的下一个节点。
通过将每个节点的prevNode与nextNode交换，列表将被反转。
a.isPalindrome()将检查给定列表是否为回文式:
声明当前将首先指向头节点的节点。
变量标志将存储一个布尔值true。
通过将列表的大小除以2来计算列表的中点。
遍历列表，直到当前指向中间节点。
使用reverseList()反转中间节点之后的列表，直到最后一个节点。该列表将在列表的后半部分。
现在，比较列表前半部分和后半部分的节点。
如果任何节点都不匹配，则将标志设置为false并中断循环。
如果循环后的标记为true，则表示该列表是回文。
如果该标志为假，则该列表不是回文。
a.display()将显示列表中存在的节点:
定义一个当前将首先指向列表开头的节点。
遍历列表，直到当前指向null为止。
在每次迭代中通过使电流指向其旁边的节点来显示每个节点。
程序:
public class PalindromeLL {
//Represent a node of the singly linked list
class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public int size;
//Represent the head and tail of the singly linked list
public Node head = null;
public Node tail = null;
//addNode() will add a new node to the list
public void addNode(int data) {
//Create a new node
Node newNode = new Node(data);
//Checks if the list is empty
if(head == null) {
//if list is empty, both head and tail will point to new node
head = newNode;
tail = newNode;
}
else {
//newNode will be added after tail such that tails next will point to newNode
tail.next = newNode;
//newNode will become new tail of the list
tail = newNode;
}
//Size will count the number of nodes present in the list
size++;
}
//reverseList() will reverse the singly linked list and return the head of the list
public Node reverseList(Node temp){
Node current = temp;
Node prevNode = null, nextNode = null;
//Swap the previous and next nodes of each node to reverse the direction of the list
while(current != null){
nextNode = current.next;
current.next = prevNode;
prevNode = current;
current = nextNode;
}
return prevNode;
}
//isPalindrome() will determine whether given list is palindrome or not.
public void isPalindromeLL(){
Node current = head;
boolean flag = true;
//Store the mid position of the list
int mid = (size%2 == 0)? (size/2) : ((size+1)/2);
//Finds the middle node in given singly linked list
for(int i=1; i<mid; i++){
current = current.next;
}
//Reverse the list after middle node to end
Node revHead = reverseList(current.next);
//Compare nodes of first half and second half of list
while(head != null && revHead != null){
if(head.data != revHead.data){
flag = false;
break;
}
head = head.next;
revHead = revHead.next;
}
if(flag)
System.out.println("Given singly linked list is a palindrome");
else
System.out.println("Given singly linked list is not a palindrome");
}
//display() will display all the nodes present in the list
public void display() {
//Node current will point to head
Node current = head;
if(head == null) {
System.out.println("List is empty");
return;
}
System.out.println("Nodes of singly linked list: ");
while(current != null) {
//Prints each node by incrementing pointer
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
PalindromeLL sList = new PalindromeLL();
//Add nodes to the list
sList.addNode(1);
sList.addNode(2);
sList.addNode(3);
sList.addNode(2);
sList.addNode(1);
sList.display();
//Checks whether given list is palindrome or not
sList.isPalindromeLL();
}
}
输出:
Nodes of singly linked list:
1 2 3 2 1
Given singly linked list is a palindrome
