CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Program to determine whether a singly linked list is the palindromeExplanationIn this program, we need to check whether given singly linked list is a palindrome or not. A palindromic list is the one which is equivalent to the reverse of itself. The list given in the above figure is a palindrome since it is equivalent to its reverse list, i.e., 1, 2, 3, 2, 1. To check whether a list is a palindrome, we traverse the list and check if any element from the starting half doesn't match with any element from the ending half, then we set the variable flag to false and break the loop. In the last, if the flag is false, then the list is palindrome otherwise not. The algorithm to check whether a list is a palindrome or not is given below. Algorithm
SolutionPython#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(); Output: 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; } Output: Nodes of the singly linked list: 1 2 3 2 1 Given singly linked list is a palindrome JAVApublic 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(); } } Output: 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(); } } Output: 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> Output: Nodes of singly linked list: 1 2 3 2 1 Given singly linked list is a palindrome
Next Topic#
