确定单向链表是否为回文串的程序

2025年3月17日 | 阅读11分钟

说明

在此程序中，我们需要检查给定的单链表是否为回文。回文列表是指与其反转列表等价的列表。

Program to determine whether a singly linked list is the palindrome

上面图示中的列表是回文列表，因为它与其反转列表等价，即 1, 2, 3, 2, 1。要检查列表是否为回文，我们遍历该列表，并检查从前半部分开始的任何元素是否与从后半部分开始的任何元素不匹配，然后我们将标志变量设置为 false 并中断循环。

最后，如果 flag 为 false，则列表是回文，否则不是。检查列表是否为回文的算法如下。

算法

创建一个名为 Node 的类，它有两个属性：data 和 next。Next 是指向链表中下一个节点的指针。
创建另一个类 Palindrome，它具有三个属性：head、tail 和 size。
addNode() 将向列表添加一个新节点
1. 创建一个新节点。
2. 它首先检查 head 是否等于 null，这意味着列表为空。
3. 如果列表为空，则 head 和 tail 都将指向新添加的节点。
4. 如果列表不为空，新节点将添加到列表末尾，使得 tail 的 next 指向新添加的节点。此新节点将成为列表的新 tail。
reverseList() 将反转列表中节点的顺序
1. Node current 将表示需要反转列表的节点。
2. Node prevNode 表示 current 的前一个节点，nextNode 表示 current 的后一个节点。
3. 通过交换每个节点的 prevNode 和 nextNode 来反转列表。
isPalindrome() 将检查给定的列表是否为回文
1. 声明一个 current 节点，它将最初指向 head 节点。
2. 变量 flag 将存储布尔值 true。
3. 通过将列表大小除以 2 来计算列表的中间点。
4. 遍历列表，直到 current 指向中间节点。
5. 使用 reverseList() 反转中间节点之后的列表直到最后一个节点。此列表将是列表的第二部分。
6. 现在，比较列表前半部分和后半部分的节点。
7. 如果任何节点不匹配，则将 flag 设置为 false 并中断循环。
8. 如果循环结束后 flag 为 true，则表示列表是回文。
9. 如果 flag 为 false，则列表不是回文。
display() 将显示列表中存在的节点
1. 定义一个节点 current，它最初将指向列表的 head。
2. 遍历列表直到 current 指向 null。
3. 通过使 current 在每次迭代中指向它的下一个节点来显示每个节点。

解决方案

Python

#Represent a node of the singly linked list
class Node:
    def __init__(self,data):
        self.data = data;
        self.next = None;
        
class Palindrome:
    #Represent the head and tail of the singly linked list
    def __init__(self):
        self.head = None;
        self.tail = None;
        self.size = 0;
        
    #addNode() will add a new node to the list
    def addNode(self, data):
        #Create a new node
        newNode = Node(data);
        
        #Checks if the list is empty
        if(self.head == None):
            #If list is empty, both head and tail will point to new node
            self.head = newNode;
            self.tail = newNode;
        else:
            #newNode will be added after tail such that tail's next will point to newNode
            self.tail.next = newNode;
            #newNode will become new tail of the list
            self.tail = newNode;
        #Size will count the number of nodes present in the list
        self.size = self.size + 1;
        
    #reverseList() will reverse the singly linked list and return the head of the list
    def reverseList(self, temp):
        current = temp;
        prevNode = None;
        nextNode = None;
        
        #Swap the previous and next nodes of each node to reverse the direction of the list
        while(current != None):
            nextNode = current.next;
            current.next = prevNode;
            prevNode = current;
            current = nextNode;
        return prevNode;
        
    #isPalindrome() will determine whether given list is palindrome or not.
    def isPalindrome(self):
        current = self.head;
        flag = True;
        
        #Store the mid position of the list
        mid = (self.size//2) if(self.size%2 == 0) else ((self.size+1)//2);
        
        #Finds the middle node in given singly linked list
        for i in range(1, mid):
            current = current.next;
            
        #Reverse the list after middle node to end
        revHead = self.reverseList(current.next);
        
        #Compare nodes of first half and second half of list
        while(self.head != None and revHead != None):
            if(self.head.data != revHead.data):
                flag = False;
                break;
                
            self.head = self.head.next;
            revHead = revHead.next;
            
        if(flag):
            print("Given singly linked list is a palindrome");
        else:
            print("Given singly linked list is not a palindrome");
            
    #display() will display all the nodes present in the list
    def display(self):
        #Node current will point to head
        current = self.head;
        
        if(self.head == None):
            print("List is empty");
            return;
        print("Nodes of singly linked list: ");
        while(current != None):
            #Prints each node by incrementing pointer
            print(current.data , end=" ");
            current = current.next;
        print();
 
sList = Palindrome();
 
#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.isPalindrome();

输出

 Nodes of the singly linked list:
1 2 3 2 1 
Given singly linked list is a palindrome

C

#include <stdio.h>
#include <stdbool.h>
 
//Represent a node of the singly linked list
struct node{
    int data;
    struct node *next;
};    
 
//Represent the head and tail of the singly linked list
struct node *head, *tail = NULL;
int size = 0;
 
//addNode() will add a new node to the list
void addNode(int data) {
    //Create a new node
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = data;
    newNode->next = NULL;
    
    //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
struct node* reverseList(struct node *temp){
    struct node *current = temp;
    struct 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.
void isPalindrome(){
    struct node *current = head;
    bool 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
    struct 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)
        printf("Given singly linked list is a palindrome\n");
    else
        printf("Given singly linked list is not a palindrome\n");
}
    
//display() will display all the nodes present in the list
void display() {
    //Node current will point to head
    struct node *current = head;
    
    if(head == NULL) {
        printf("List is empty\n");
        return;
    }
    printf("Nodes of singly linked list: \n");
    while(current != NULL) {
        //Prints each node by incrementing pointer
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}
    
int main()
{
    //Add nodes to the list
    addNode(1);
    addNode(2);
    addNode(3);
    addNode(2);
    addNode(1);
    
    display();
    
    //Checks whether given list is palindrome or not
    isPalindrome();
    
    return 0;
}

输出

Nodes of the singly linked list:
1 2 3 2 1 
Given singly linked list is a palindrome

JAVA

public class Palindrome {
    
    //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 isPalindrome(){
        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) {
        
        Palindrome sList = new Palindrome();
        
        //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.isPalindrome();
    }
}

输出

Nodes of singly linked list: 
1 2 3 2 1 
Given singly linked list is a palindrome

C#

using System;
                    
public class CreateList
{
    //Represent a node of the singly linked list
    public class Node<T>{
        public T data;
        public Node<T> next;
        
        public Node(T value) {
            data = value;
            next = null;
        }
    }
        
    public class Palindrome<T>{
        //Represent the head and tail of the singly linked list
        public Node<T> head = null;             
         public Node<T> tail = null;
        public int size;
        
        //addNode() will add a new node to the list
        public void addNode(T data) {
            //Create a new node
            Node<T> newNode = new Node<T>(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<T> reverseList(Node<T> temp){
            Node<T> current = temp;
            Node<T> 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 isPalindrome(){
            Node<T> 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<T> revHead = reverseList(current.next);
 
            //Compare nodes of first half and second half of list
            while(head != null && revHead != null){
                if(!(head.data.Equals(revHead.data))){
                    flag = false;
                    break;
                }
                head = head.next;
                revHead = revHead.next;
            }
 
            if(flag)
                Console.WriteLine("Given singly linked list is a palindrome");
            else
                Console.WriteLine("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<T> current = head;
            
            if(head == null) {
                Console.WriteLine("List is empty");
                return;
            }
            Console.WriteLine("Nodes of singly linked list: ");
            while(current != null) {
                //Prints each node by incrementing pointer
                Console.Write(current.data + " ");
                current = current.next;
            }
            Console.WriteLine();
        }
    }
    
    public static void Main()
    {
        Palindrome<int> sList = new Palindrome<int>();
        
        //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.isPalindrome();    
    }
}           

输出

Nodes of singly linked list: 
1 2 3 2 1 
Given singly linked list is a palindrome

PHP

<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of singly linked list
class Node{
    public $data;
    public $next;
    
    function __construct($data){
        $this->data = $data;
        $this->next = NULL;
    }
}
class Palindrome{
    //Represent the head and tail of the singly linked list
    public $head;
    public $tail;
    function __construct(){
        $this->head = NULL;
        $this->tail = NULL;
        $this->size = 0;
    }
    
    //addNode() will add a new node to the list
    function addNode($data) {
        //Create a new node
        $newNode = new Node($data);
        
        //Checks if the list is empty
        if($this->head == NULL) {
            //If list is empty, both head and tail will point to new node
            $this->head = $newNode;
            $this->tail = $newNode;
        }
        else {
            //newNode will be added after tail such that tail's next will point to newNode
            $this->tail->next = $newNode;
            //newNode will become new tail of the list
            $this->tail = $newNode;
        }
        //Size will count the number of nodes present in the list
        $this->size++;
    }
    
    //reverseList() will reverse the singly linked list and return the head of the list
    function reverseList($temp){
        $current = $temp;
        $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.
    function isPalindrome(){
        $current = $this->head;
        $flag = true;
        
        //Store the mid position of the list
        $mid = ($this->size%2 == 0)? ($this->size/2) : (($this->size+1)/2);
        
        //Finds the middle node in given singly linked list
        for($i=1; $i<$mid; $i++){
            $current = $current->next;
        }
        
        //Reverse the list after middle node to end
        $revHead = $this->reverseList($current->next);
 
        //Compare nodes of first half and second half of list
        while($this->head != null && $revHead != null){
            if($this->head->data != $revHead->data){
                $flag = false;
                break;
            }
            $this->head = $this->head->next;
            $revHead = $revHead->next;
        }
 
        if($flag)
            print("Given singly linked list is a palindrome <br>");
        else
            print("Given singly linked list is not a palindrome <br>");
    }
    
    //display() will display all the nodes present in the list
    function display() {
        //Node current will point to head
        $current = $this->head;
        
        if($this->head == NULL) {
            print("List is empty <br>");
            return;
        }
        print("Nodes of singly linked list: <br>");
        while($current != NULL) {
            //Prints each node by incrementing pointer
            print($current->data . " ");
            $current = $current->next;
        }
        print("<br>");
    }
}
    
$sList = new Palindrome();
        
//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->isPalindrome();
?>
</body>
</html>

输出

 Nodes of singly linked list: 
1 2 3 2 1 
Given singly linked list is a palindrome

下一主题#

确定单向链表是否为回文串的程序

说明

算法

解决方案

Python

C

JAVA

C#

PHP

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

程序

确定单向链表是否为回文串的程序

说明

算法

解决方案

Python

C

JAVA

C#

PHP

相关帖子

计算立方体表面积的程序

编写查找六棱柱（Hexagonal Prism）面积的程序

从双向链表开头删除新节点的程序

打印图案 3 的程序

打印数组中元素数量的程序

打印数字图案 5 的程序

计算圆锥体积的程序

打印星型图案 1 的程序

从双向链表中删除重复元素的程序

计算长方体表面积的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器