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 node struct Node { int data; struct Node* next; }; // Function to check if elements of // linked list are present in pair bool 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 List void 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 function int 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 node class Node: def __init__( self ): self .data = 0 self . next = None # Function to check if elements of # linked list are present in pair def 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 List def 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 code first = 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 elements if ( 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> |
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 node struct 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 pair bool 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 function int 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 pair import java.util.*; // A linked list node class 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 node class Node: def __init__( self , value): self .data = value self . next = None # function to check if elements of # linked list are preset in pair def 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 -> 1 head = 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 elements if (isPair(head) is True ): print ( "Yes" ) else : print ( "No" ) |
C#
// C# program to check if elements of // linked lists are present in pair using System; using System.Collections.Generic; // A linked list node public 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 node class Node{ constructor(value){ this .data = value; this .next = null ; } } // function to check if elements of linked // list are preseint in pair function 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 elements if (isPair(head)) console.log( "Yes" ); else console.log( "No" ) // This code is contributed by Yash Agarwal(yashagarwal2852002) |
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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!