Given a linked list. Find the first element from the left which appears more than once. If all the elements are unique then print -1.
Examples:
Input : 1 2 3 4 3 2 1
Output : 1
In this linked list the element 1 occurs two times
and it is the first element to satisfy the condition.
Hence, the answer is 1.
Input : 1 2, 3, 4, 5
Output : -1
All the elements are unique. Hence, the answer is -1.
Approach:
- Count the frequency of all the elements of the linked list using a map.
- Now, traverse the linked list again to find the first element from the left whose frequency is greater than 1.
- If no such element exists then print -1.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// A linked list nodeclass Node {public: int data; Node* next;};// Given a reference (pointer to pointer)// to the head of a list and an int,// appends a new node at the endvoid append(Node** head_ref, int new_data){ // allocate node Node* new_node = new Node(); Node* last = *head_ref; // put in the data new_node->data = new_data; // This new node is going to be // the last node, so make next of // it as NULL new_node->next = NULL; // If the Linked List is empty, // then make the new node as head if (*head_ref == NULL) { *head_ref = new_node; return; } // Else traverse till the last node while (last->next != NULL) last = last->next; // Change the next of last node last->next = new_node; return;}int getFirstDuplicate(Node* node){ // Unordered map to store the // frequency of elements unordered_map<int, int> mp; Node* head = node; // update frequency of all the elements while (node != NULL) { mp[node->data]++; node = node->next; } node = head; // the first node from the left which // appears more than once is the answer while (node != NULL) { if (mp[node->data] > 1) return node->data; node = node->next; } // all the nodes are unique return -1;}// driver codeint main(){ // Start with the empty list Node* head = NULL; // Insert element append(&head, 6); append(&head, 2); append(&head, 1); append(&head, 6); append(&head, 2); append(&head, 1); cout << getFirstDuplicate(head); return 0;} |
Java
// Java implementation of // the above approachimport java.util.*;class GFG{// A linked list nodestatic class Node { int data; Node next;};static Node head_ref; // Given a reference (pointer to // pointer) to the head of a list // and an int, appends a new node // at the endstatic void append(int new_data){ // allocate node Node new_node = new Node(); Node last = head_ref; // put in the data new_node.data = new_data; // This new node is going // to be the last node, // so make next of it as // null new_node.next = null; // If the Linked List is // empty, then make the // new node as head if (head_ref == null) { head_ref = new_node; return; } // Else traverse till the // last node while (last.next != null) last = last.next; // Change the next of // last node last.next = new_node; return;}static int getFirstDuplicate(Node node){ // Unordered map to store the // frequency of elements HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); Node head = node; // update frequency of all // the elements while (node != null) { if(mp.containsKey(node.data)) mp.put(node.data, mp.get(node.data) + 1); else mp.put(node.data, 1); node = node.next; } node = head; // the first node from the // left which appears more // than once is the answer while (node != null) { if (mp.get(node.data) > 1) return node.data; node = node.next; } // all the nodes are unique return -1;}// Driver codepublic static void main(String[] args){ // Start with the empty list head_ref = null; // Insert element append(6); append(2); append(1); append(6); append(2); append(1); System.out.print( getFirstDuplicate(head_ref));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of above approach# Link list node class Node : def __init__(self): self.data = 0 self.next = None# Given a reference (pointer to pointer)# to the head of a list and an int,# appends a node at the enddef append(head_ref, new_data): # allocate node new_node = Node() last = head_ref # put in the data new_node.data = new_data # This node is going to be # the last node, so make next of # it as None new_node.next = None # If the Linked List is empty, # then make the node as head if (head_ref == None) : head_ref = new_node return head_ref # Else traverse till the last node while (last.next != None): last = last.next # Change the next of last node last.next = new_node return head_refdef getFirstDuplicate(node): # Unordered map to store the # frequency of elements mp = dict() head = node # update frequency of all the elements while (node != None) : mp[node.data] = mp.get(node.data, 0) + 1 node = node.next node = head # the first node from the left which # appears more than once is the answer while (node != None) : if (mp[node.data] > 1): return node.data node = node.next # all the nodes are unique return -1# Driver code# Start with the empty listhead = None# Insert elementhead = append(head, 6)head = append(head, 2)head = append(head, 1)head = append(head, 6)head = append(head, 2)head = append(head, 1)print(getFirstDuplicate(head))# This code is contributed by Arnab Kundu |
C#
// C# implementation of // the above approachusing System;using System.Collections.Generic;class GFG{// A linked list nodepublic class Node { public int data; public Node next;}; static Node head_ref; // Given a reference (pointer to // pointer) to the head of a list // and an int, appends a new node // at the endstatic void append(int new_data){ // allocate node Node new_node = new Node(); Node last = head_ref; // put in the data new_node.data = new_data; // This new node is going // to be the last node, // so make next of it as // null new_node.next = null; // If the Linked List is // empty, then make the // new node as head if (head_ref == null) { head_ref = new_node; return; } // Else traverse till the // last node while (last.next != null) last = last.next; // Change the next of // last node last.next = new_node; return;}static int getFirstDuplicate(Node node){ // Unordered map to store the // frequency of elements Dictionary<int, int> mp = new Dictionary<int, int>(); Node head = node; // update frequency of all // the elements while (node != null) { if(mp.ContainsKey(node.data)) mp[node.data]++; else mp.Add(node.data, 1); node = node.next; } node = head; // the first node from the // left which appears more // than once is the answer while (node != null) { if (mp[node.data] > 1) return node.data; node = node.next; } // all the nodes are // unique return -1;}// Driver codepublic static void Main(String[] args){ // Start with the empty list head_ref = null; // Insert element append(6); append(2); append(1); append(6); append(2); append(1); Console.Write( getFirstDuplicate(head_ref));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of // the above approach// A linked list nodeclass Node { constructor() { this.data = 0; this.next = null; }}; var head_ref; // Given a reference (pointer to // pointer) to the head of a list // and an int, appends a new node // at the endfunction append(new_data){ // allocate node var new_node = new Node(); var last = head_ref; // put in the data new_node.data = new_data; // This new node is going // to be the last node, // so make next of it as // null new_node.next = null; // If the Linked List is // empty, then make the // new node as head if (head_ref == null) { head_ref = new_node; return; } // Else traverse till the // last node while (last.next != null) last = last.next; // Change the next of // last node last.next = new_node; return;}function getFirstDuplicate(node){ // Unordered map to store the // frequency of elements var mp = new Map(); var head = node; // update frequency of all // the elements while (node != null) { if(mp.has(node.data)) mp.set(node.data , mp.get(node.data)+1); else mp.set(node.data, 1); node = node.next; } node = head; // the first node from the // left which appears more // than once is the answer while (node != null) { if (mp.get(node.data) > 1) return node.data; node = node.next; } // all the nodes are // unique return -1;}// Driver code// Start with the empty listhead_ref = null;// Insert elementappend(6);append(2);append(1);append(6);append(2);append(1);document.write(getFirstDuplicate(head_ref));</script> |
Output:
6
Time Complexity: O(N)
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!
