Given a Linked list of integers containing duplicate elements, the task is to print all the duplicates in the given Linked List.
Examples:
Input: list = [10, 20, 30, 20, 20, 30, 40, 50, -20, 60, 60, -20, -20]
Output: [20, 30, -20, 60]Input: list = [5, 7, 5, 1, 7]
Output: [5, 7]
Naive Approach: To basic way to solve the problem is as follows:
- We traverse the whole linked list.
- For each node, we check in the remaining list whether the duplicate node exists or not.
- If it does then store it in an array.
- In the end, print all elements of the array
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Representation of nodestruct Node { int data; Node* next;};// Function to insert a node at the beginningvoid insert(Node** head, int item){ Node* temp = new Node(); temp->data = item; temp->next = *head; *head = temp;}// Function to print duplicate nodes in// the linked listvector<int> printDuplicatesInList(Node* head){ vector<int> dupes; while (head->next != NULL) { // Starting from the next node Node* ptr = head->next; while (ptr != NULL) { // If some duplicate node is found if (head->data == ptr->data) { dupes.push_back(head->data); break; } ptr = ptr->next; } head = head->next; } // Return the count of duplicate nodes return dupes;}// Driver codeint main(){ Node* head = NULL; insert(&head, 5); insert(&head, 7); insert(&head, 5); insert(&head, 1); insert(&head, 7); // Function Call vector<int> dupesInList = printDuplicatesInList(head); for (int i = 0; i < dupesInList.size(); i++) cout << dupesInList[i] << ", "; cout << endl; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class Node { int data; Node next;}public class PrintDuplicateNodes { // Function to insert a node at the beginning static void insert(Node[] head, int item) { Node temp = new Node(); temp.data = item; temp.next = head[0]; head[0] = temp; } // Function to print duplicate nodes in the linked list static List<Integer> printDuplicatesInList(Node head) { List<Integer> dupes = new ArrayList<>(); while (head.next != null) { // Starting from the next node Node ptr = head.next; while (ptr != null) { // If some duplicate node is found if (head.data == ptr.data) { dupes.add(head.data); break; } ptr = ptr.next; } head = head.next; } // Return the list of duplicate nodes return dupes; } // Driver code public static void main(String[] args) { Node[] head = new Node[1]; head[0] = null; insert(head, 5); insert(head, 7); insert(head, 5); insert(head, 1); insert(head, 7); // Function Call List<Integer> dupesInList = printDuplicatesInList(head[0]); for (int i = 0; i < dupesInList.size(); i++) { System.out.print(dupesInList.get(i) + ", "); } System.out.println(); }}//This code is contributed by chinmaya121221 |
Python3
# Representation of nodeclass Node: def __init__(self, data): self.data = data self.next = None# Function to insert a node at the beginningdef insert(head, item): new_node = Node(item) new_node.next = head head = new_node return head# Function to print duplicate nodes in the linked listdef print_duplicates_in_list(head): dupes = [] while head is not None: ptr = head.next while ptr is not None: if head.data == ptr.data: dupes.append(head.data) break ptr = ptr.next head = head.next return dupes# Driver codeif __name__ == "__main__": head = None head = insert(head, 5) head = insert(head, 7) head = insert(head, 5) head = insert(head, 1) head = insert(head, 7) # Function call dupes_in_list = print_duplicates_in_list(head) for item in dupes_in_list: print(item, end=", ") print() #Contributed by Aditi Tyagi |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;// Representation of nodeclass Node{ public int data; public Node next;}class Program{ // Function to insert a node at the beginning static void Insert(ref Node head, int item) { Node temp = new Node { data = item, next = head }; head = temp; } // Function to print duplicate nodes in the linked list static List<int> PrintDuplicatesInList(Node head) { List<int> dupes = new List<int>(); while (head.next != null) { // Starting from the next node Node ptr = head.next; while (ptr != null) { // If some duplicate node is found if (head.data == ptr.data) { dupes.Add(head.data); break; } ptr = ptr.next; } head = head.next; } // Return the count of duplicate nodes return dupes; } // Driver code static void Main(string[] args) { Node head = null; Insert(ref head, 5); Insert(ref head, 7); Insert(ref head, 5); Insert(ref head, 1); Insert(ref head, 7); // Function Call List<int> dupesInList = PrintDuplicatesInList(head); foreach (int item in dupesInList) { Console.Write(item + ", "); } Console.WriteLine(); }}// this code is contributed by uttamdp_10 |
Javascript
// Define a class for the linked list nodeclass Node { constructor(data) { this.data = data; this.next = null; }}// Function to insert a node at the beginning of the linked listfunction insert(head, item) { const temp = new Node(item); temp.next = head[0]; head[0] = temp;}// Function to print duplicate nodes in the linked listfunction printDuplicatesInList(head) { const dupes = []; while (head.next !== null) { // Starting from the next node let ptr = head.next; while (ptr !== null) { // If some duplicate node is found if (head.data === ptr.data) { dupes.push(head.data); break; } ptr = ptr.next; } head = head.next; } // Return the list of duplicate nodes return dupes;}// Driver codeconst head = [null];insert(head, 5);insert(head, 7);insert(head, 5);insert(head, 1);insert(head, 7);// Function Callconst dupesInList = printDuplicatesInList(head[0]);for (let i = 0; i < dupesInList.length; i++) { process.stdout.write(dupesInList[i] + ", ");}console.log(); |
Output
7, 5,
Time Complexity: O(N2), where N is the number of elements in the list.
Auxiliary Space: O(N), an additional vector is used to store the duplicate values.
Printing duplicates from a list of integers using Hashing:
- We traverse the whole linked list.
- Create a hashtable
- For each node
- If it is not present in the hashtable, insert it with frequency 1
- If it is already present, update its frequency
- At the end, print all elements of the hashtable with frequency more than 1
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Representation of nodestruct Node { int data; Node* next;};// Function to insert a node at the beginningvoid insert(Node** head, int item){ Node* temp = new Node(); temp->data = item; temp->next = *head; *head = temp;}// Function to print duplicate nodes in// the linked listmap<int, int> printDuplicatesInList(Node* head){ // Create a hash table insert head map<int, int> M; // Traverse through remaining nodes int count = 0; for (Node* curr = head; curr != NULL; curr = curr->next) { // If the current element // is not found then insert // current element with // frequency 1 if (M.find(curr->data) == M.end()) M[curr->data] = 1; // Else update the frequency else M[curr->data]++; } // Return the map with frequency return M;}// Driver codeint main(){ Node* head = NULL; insert(&head, 5); insert(&head, 7); insert(&head, 5); insert(&head, 1); insert(&head, 7); // Function Call map<int, int> dupesInList = printDuplicatesInList(head); // Traverse the map to print the // frequency for (auto& it : dupesInList) { if (it.second > 1) cout << it.first << ", "; } cout << endl; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class Node { int data; Node next;}public class PrintDuplicateNodes { // Function to insert a node at the beginning static void insert(Node[] head, int item) { Node temp = new Node(); temp.data = item; temp.next = head[0]; head[0] = temp; } // Function to print duplicate nodes in the linked list static Map<Integer, Integer> printDuplicatesInList(Node head) { Map<Integer, Integer> M = new HashMap<>(); // Traverse through remaining nodes Node curr = head; while (curr != null) { // If the current element is not found then insert // the current element with frequency 1 if (!M.containsKey(curr.data)) { M.put(curr.data, 1); } // Else update the frequency else { M.put(curr.data, M.get(curr.data) + 1); } curr = curr.next; } // Return the map with frequency return M; } // Driver code public static void main(String[] args) { Node[] head = new Node[1]; head[0] = null; insert(head, 5); insert(head, 7); insert(head, 5); insert(head, 1); insert(head, 7); // Function Call Map<Integer, Integer> dupesInList = printDuplicatesInList(head[0]); // Traverse the map to print the frequency for (Map.Entry<Integer, Integer> entry : dupesInList.entrySet()) { if (entry.getValue() > 1) { System.out.print(entry.getKey() + ", "); } } System.out.println(); }}//This code is contributed by chinmaya121221 |
Python3
class Node: def __init__(self, data): self.data = data self.next = Nonedef insert(head, item): temp = Node(item) temp.next = head[0] head[0] = tempdef print_duplicates_in_list(head): M = {} # Traverse through the linked list curr = head while curr is not None: # If the current element is not found, insert it with frequency 1 if curr.data not in M: M[curr.data] = 1 # Else update the frequency else: M[curr.data] += 1 curr = curr.next # Return a dictionary with frequencies return M# Driver codehead = [None]insert(head, 5)insert(head, 7)insert(head, 5)insert(head, 1)insert(head, 7)# Function Calldupes_in_list = print_duplicates_in_list(head[0])# Traverse the dictionary to print elements with frequency > 1for key, value in dupes_in_list.items(): if value > 1: print(key, end=", ")print() |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;// Representation of nodeclass Node{ public int data; public Node next;}class Program{ // Function to insert a node at the beginning static void Insert(ref Node head, int item) { Node temp = new Node { data = item, next = head }; head = temp; } // Function to print duplicate nodes in the linked list static Dictionary<int, int> PrintDuplicatesInList(Node head) { // Create a dictionary to insert head Dictionary<int, int> M = new Dictionary<int, int>(); // Traverse through remaining nodes for (Node curr = head; curr != null; curr = curr.next) { // If the current element is not found then insert // current element with frequency 1 if (!M.ContainsKey(curr.data)) M[curr.data] = 1; // Else update the frequency else M[curr.data]++; } // Return the dictionary with frequency return M; } // Driver code static void Main(string[] args) { Node head = null; Insert(ref head, 5); Insert(ref head, 7); Insert(ref head, 5); Insert(ref head, 1); Insert(ref head, 7); // Function Call Dictionary<int, int> dupesInList = PrintDuplicatesInList(head); // Traverse the dictionary to print the frequency foreach (var kvp in dupesInList) { if (kvp.Value > 1) Console.Write(kvp.Key + ", "); } Console.WriteLine(); }}// this code is contributed by uttamdp_10 |
Javascript
// Define a class for the linked list nodeclass Node { constructor(data) { this.data = data; this.next = null; }}// Function to insert a node at the beginning of the linked listfunction insert(head, item) { // Create a new node with the given data const temp = new Node(item); // Set the next pointer of the new node to the current head temp.next = head[0]; // Update the head to the new node head[0] = temp;}// Function to find duplicate nodes in the linked list and their frequenciesfunction printDuplicatesInList(head) { // Create a Map to store the frequency of each element const frequencyMap = new Map(); let curr = head; // Traverse through the linked list while (curr !== null) { // If the current element is not found in the Map, add it with a frequency of 1 if (!frequencyMap.has(curr.data)) { frequencyMap.set(curr.data, 1); } // If the element already exists in the Map, update its frequency else { frequencyMap.set(curr.data, frequencyMap.get(curr.data) + 1); } curr = curr.next; } // Create an array to store the duplicate keys (elements with frequency > 1) const duplicateKeys = []; for (const [key, value] of frequencyMap.entries()) { if (value > 1) { duplicateKeys.push(key); } } return duplicateKeys;}// Create the head of the linked listconst head = [null];// Insert elements at the beginning of the linked listinsert(head, 5);insert(head, 7);insert(head, 5);insert(head, 1);insert(head, 7);// Find and print duplicate keys in the linked listconst duplicateKeys = printDuplicatesInList(head[0]);// Print the duplicate keysfor (let i = 0; i < duplicateKeys.length; i++) { process.stdout.write(duplicateKeys[i] + ", ");}console.log(); |
Output
5, 7,
Time Complexity: O(N*logN), for traversing the list O(N) time will consume, and to find the element in msp, O(Log N) time will be taken, So the time complexity of the above approach is O(N*logN).
Auxiliary Space: O(N), map is used to store the elements.
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!
Share your thoughts in the comments
