判断单链表是否为回文的Java程序

1 简介

在此程序中，我们需要检查给定的单链表是否是回文。回文列表是与之相反的列表。

上图中给出的列表是回文，因为它等同于其反向列表，即1、2、3、2、1。要检查列表是否是回文，我们遍历该列表并检查是否有来自开始的一半与结束的任何元素都不匹配，然后将变量标志设置为false并中断循环。

最后，如果标志为假，则列表为回文，否则为非。下面给出了检查列表是否为回文式的算法：

2 算法思路

• 创建一个具有两个属性的类Node：data和next。下一个是指向列表中下一个节点的指针。
• 创建另一个具有三个属性的回文类：头，尾和大小。
• addNode（）将向列表添加一个新节点：
  • 创建一个新节点。
  • 它首先检查head是否等于null，这意味着列表为空。
  • 如果列表为空，则头和尾都将指向新添加的节点。
  • 如果列表不为空，则新节点将被添加到列表的末尾，使得尾部的下一个将指向新添加的节点。这个新节点将成为列表的新尾部。
• 当前节点将表示需要从其反向列表的节点。
• 节点prevNode表示当前节点的前一个节点，nextNode表示当前节点的下一个节点。
• 通过将每个节点的prevNode与nextNode交换，可以反转该列表。
• 声明一个节点电流，该电流最初将指向头节点。
• 变量标志将存储一个布尔值true。
• 用列表的大小除以2计算列表的中点。
• 遍历列表，直到当前指向中间节点。
• 使用reverseList（）反转中间节点之后的列表，直到最后一个节点。该列表将在列表的后半部分。
• 现在，比较列表上半部分和下半部分的节点。
• 如果任何一个节点都不匹配，则将标志设置为false并中断循环。
• 如果该标志在循环之后为真，则表明该列表是回文。
• 如果该标志为假，则该列表不是回文。
• 定义一个节点，该节点将初始指向列表的开头。
• 遍历列表，直到当前指向null。
• 通过在每次迭代中使节点指向其旁边的节点来显示每个节点。

3 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
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 tail's 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