Given a singly linked list of integers. The task is to check if each element in the linked list is present in a pair i.e. all elements occur even no. of times.
Examples:
Input: 1 -> 2 -> 3 -> 3 -> 1 -> 2 Output: Yes Input: 10 -> 20 -> 30 -> 20 Output: No
Approach:
- Initialize a temp node pointing to head.
- Take a variable to calculate XOR of all elements.
- Start traversing linked list and keep calculating the XOR with node->data.
- Return true if XOR is 0, else return false.
Below is the implementation of above approach:
C++
// C++ program to check if elements of// linked lists are present in pair#include <bits/stdc++.h>using namespace std;// A linked list nodestruct Node { int data; struct Node* next;};// Function to check if elements of// linked list are present in pairbool isPair(struct Node* head){ int xxor = 0; struct Node* temp = head; while (temp != NULL) { xxor ^= temp->data; temp = temp->next; } return xxor;}// Function to add a node at the// beginning of Linked Listvoid push(struct Node** head_ref, int new_data){ /* allocate node */ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list of the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node;}// Driver program to test above functionint main(){ struct Node* first = NULL; /* First constructed linked list is: 10 -> 34 -> 1 -> 10 -> 34 -> 1 */ push(&first, 1); push(&first, 34); push(&first, 10); push(&first, 1); push(&first, 34); push(&first, 10); // Calling function to check pair elements if (!isPair(first)) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0;} |
Java
// Java program to check if elements of // linked lists are present in pair // Node Class class Node{ int data; Node next; // Constructor to create a new node Node(int d) { data = d; next = null; }}class SLL { // function to insert a node at the beginning // of the Singly Linked List static Node push(Node head, int data) { Node newNode = new Node(data); newNode.next = head; head = newNode; return head; } // Function to check if elements of // linked list are present in pair static boolean isPair(Node head) { int xxor = 0; Node temp = head; while (temp != null) { xxor ^= temp.data; temp = temp.next; } return xxor != 0; } // Driver code public static void main(String[] args) { Node head = null; // First constructed linked list // 10 -> 34 -> 1 -> 10 -> 34 -> 1 head = push(head, 1); head = push(head, 34); head = push(head, 10); head = push(head, 1); head = push(head, 34); head = push(head, 10); // Calling function to check pair elements if (!isPair(head)) { System.out.println("Yes"); } else { System.out.println("No"); } }}// This code is contributed by Vivekkumar Singh |
Python3
# Python3 program to check if elements of# linked lists are present in pair# A linked list nodeclass Node: def __init__(self): self.data = 0 self.next = None# Function to check if elements of# linked list are present in pairdef isPair( head): xxor = 0 temp = head while (temp != None) : xxor = xxor ^ temp.data temp = temp.next return xxor# Function to add a node at the# beginning of Linked Listdef push( head_ref, new_data): # allocate node new_node = Node() # put in the data new_node.data = new_data # link the old list of the new node new_node.next = (head_ref) # move the head to point to the new node (head_ref) = new_node return head_ref# Driver codefirst = None# First constructed linked list is: # 10 . 34 . 1 . 10 . 34 . 1 first = push(first, 1)first = push(first, 34)first = push(first, 10)first = push(first, 1)first = push(first, 34)first = push(first, 10)# Calling function to check pair elementsif (not isPair(first)): print( "Yes" ) else : print( "No" ) # This code is contributed by Arnab Kundu |
C#
// C# program to check if elements of // linked lists are present in pair using System;// Node Class public class Node{ public int data; public Node next; // Constructor to create a new node public Node(int d) { data = d; next = null; }}public class SLL { // function to insert a node at the beginning // of the Singly Linked List static Node push(Node head, int data) { Node newNode = new Node(data); newNode.next = head; head = newNode; return head; } // Function to check if elements of // linked list are present in pair static Boolean isPair(Node head) { int xxor = 0; Node temp = head; while (temp != null) { xxor ^= temp.data; temp = temp.next; } return xxor != 0; } // Driver code public static void Main(String[] args) { Node head = null; // First constructed linked list // 10 -> 34 -> 1 -> 10 -> 34 -> 1 head = push(head, 1); head = push(head, 34); head = push(head, 10); head = push(head, 1); head = push(head, 34); head = push(head, 10); // Calling function to check pair elements if (!isPair(head)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }}// This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to check if elements of // linked lists are present in pair // Node Class class Node { // Constructor to create a new node constructor(d) { this.data = d; this.next = null; } } // function to insert a node at the beginning // of the Singly Linked List function push(head, data) { var newNode = new Node(data); newNode.next = head; head = newNode; return head; } // Function to check if elements of // linked list are present in pair function isPair(head) { var xxor = 0; var temp = head; while (temp != null) { xxor ^= temp.data; temp = temp.next; } return xxor != 0; } // Driver code var head = null; // First constructed linked list // 10 -> 34 -> 1 -> 10 -> 34 -> 1 head = push(head, 1); head = push(head, 34); head = push(head, 10); head = push(head, 1); head = push(head, 34); head = push(head, 10); // Calling function to check pair elements if (!isPair(head)) { document.write("Yes"); } else { document.write("No"); } </script> |
Output
Yes
Time Complexity: O(n), where n is the number of nodes in the linked list
Auxiliary Space: O(1)
Method-2(Using Map)
We will traverse the complete linked list from left to right and store all elements in map with their frequency.
After completely traversing the linked list, we will find an element in the map which frequency is not even if any element is found we print “No” otherwise print “Yes”.
Below is the implementation of above approach:
C++
// C++ program to check if elements of// linked lists are present in pair#include <bits/stdc++.h>using namespace std;// A linked list nodestruct Node { int data; struct Node* next; Node(int value){ this->data = value; this->next = NULL; }};// Function to check if elements of// linked list are present in pairbool isPair(Node* head){ unordered_map<int, int> mp; while(head != NULL){ mp[head->data]++; head = head->next; } // traversing the map for(auto i: mp) if(i.second % 2 == 1) return false; return true;}// Driver program to test above functionint main(){ /* First constructed linked list is: 10 -> 34 -> 1 -> 10 -> 34 -> 1 */ struct Node* head = new Node(10); head->next = new Node(34); head->next->next = new Node(1); head->next->next->next = new Node(10); head->next->next->next->next = new Node(34); head->next->next->next->next->next = new Node(1); //calling function to check pair elements if (isPair(head)) cout << "Yes" << endl; else cout << "No" << endl; return 0;}// This code is contributed by Kirti Agarwal(kirtiagarwal23121999) |
Java
// Java program to check if elements of// linked lists are present in pairimport java.util.*;// A linked list nodeclass Node { int data; Node next; Node(int value){ this.data = value; this.next = null; }}class Main{ // Function to check if elements of // linked list are present in pair static boolean isPair(Node head) { Map<Integer, Integer> mp = new HashMap<>(); while(head != null){ mp.put(head.data, mp.getOrDefault(head.data, 0) + 1); head = head.next; } // traversing the map for(Map.Entry<Integer, Integer> entry : mp.entrySet()) if(entry.getValue() % 2 == 1) return false; return true; } // Driver program to test above function public static void main(String args[]) { /* First constructed linked list is: 10 -> 34 -> 1 -> 10 -> 34 -> 1 */ Node head = new Node(10); head.next = new Node(34); head.next.next = new Node(1); head.next.next.next = new Node(10); head.next.next.next.next = new Node(34); head.next.next.next.next.next = new Node(1); // calling function to check pair elements if (isPair(head)) System.out.println("Yes"); else System.out.println("No"); }} |
Python
# python program for the above approach# a linked list nodeclass Node: def __init__(self, value): self.data = value self.next = None # function to check if elements of# linked list are preset in pairdef isPair(head): mp = {} while(head is not None): if(mp.get(head.data) is not None): mp[head.data] += 1 else: mp[head.data] = 1 head = head.next # traversing the map for x, y in mp.items(): if(y % 2 == 1): return False return True # driver program to test above function# First constructed linked list is:# 10 -> 34 -> 1 -> 10 -> 34 -> 1head = Node(10)head.next = Node(34)head.next.next = Node(1)head.next.next.next = Node(10)head.next.next.next.next = Node(34)head.next.next.next.next.next = Node(1)# calling functions to check pair elementsif(isPair(head) is True): print("Yes")else: print("No") |
C#
// C# program to check if elements of// linked lists are present in pairusing System;using System.Collections.Generic;// A linked list nodepublic class Node { public int data; public Node next; public Node(int value) { this.data = value; this.next = null; }};public class GFG { // Function to check if elements of // linked list are present in pair public static bool isPair(Node head) { Dictionary<int, int> mp = new Dictionary<int, int>(); while (head != null) { if (mp.ContainsKey(head.data)) { mp[head.data]++; } else { mp.Add(head.data, 1); } head = head.next; } // traversing the dictionary foreach(KeyValuePair<int, int> i in mp) { if (i.Value % 2 == 1) { return false; } } return true; } // Driver program to test above function public static void Main() { /* First constructed linked list is: 10 -> 34 -> 1 -> 10 -> 34 -> 1 */ Node head = new Node(10); head.next = new Node(34); head.next.next = new Node(1); head.next.next.next = new Node(10); head.next.next.next.next = new Node(34); head.next.next.next.next.next = new Node(1); // calling function to check pair elements if (isPair(head)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }}// This code is contributed by phasing17 |
Javascript
// JavaScript Program to check if elements of// linked lists are present in pair// a linked list nodeclass Node{ constructor(value){ this.data = value; this.next = null; }}// function to check if elements of linked// list are preseint in pairfunction isPair(head){ let mp = new Map(); while(head != null){ if(mp.has(head.data)){ mp.set(head.data, mp.get(head.data) + 1); }else{ mp.set(head.data, 1); } head = head.next; } // traversing the map mp.forEach(function(value, key){ if(value % 2 == 1) return false; }) return true;}// driver program to test above function/* First constructed linked list is:10 -> 34 -> 1 -> 10 -> 34 -> 1 */let head = new Node(10);head.next = new Node(34);head.next.next = new Node(1);head.next.next.next = new Node(10);head.next.next.next.next = new Node(34);head.next.next.next.next.next = new Node(1);// calling function to check pair elementsif(isPair(head)) console.log("Yes");else console.log("No")// This code is contributed by Yash Agarwal(yashagarwal2852002) |
Output
Yes
Time Complexity: O(N) where N is the number of elements in given Linked List.
Auxiliary Space: O(N) due to map data structure.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
