Program to find the duplicate element in the linked list

An algorithm to find the first duplicate element in the single linked list in javascript.

Example

Input:
10 -> 2 -> 5 -> 7 -> 9 -> 1 -> 2
1 -> 2 -> 3 -> 4 -> 5

Output:
2
-1

2 is the first duplicate element in the first list so we returned it. As second list does not contains any duplicate we returned -1.

There are two different ways in which we can solve this problem.

Method 1: Using nested loops O(n ^ 2).

Implementation

• We will use two nested loops to find the first duplicate element in the list.
• In the outer loop we will get the current element and the sublist.
• Then we will use an inner loop to iterate the sublist and check if there is any element matching the parent loop element.

let findDuplicate = (head) => {
    //loop the list
    while(head){
      
      //get the elm from the outer loop
      let elm = head.element;
      
      //Get the list after current elm
      let subList = head.next;
      while(subList){
        //If elm is present in the sublist
        //Return it
        if(elm === subList.element){
          return elm;
        }
        
        //next elm of sublist
        subList = subList.next;
      }
      
      //next elm of main list
      head = head.next;
    }
  
  return -1;
}

Input:
let ll = new LinkedList();
ll.append(1);
ll.append(2);
ll.append(3);
ll.append(4);
ll.append(2);
ll.append(5);
let head = ll.getHead();
console.log(findDuplicate(head));

Output:
2

Time complexity: O(n ^ 2).
Space complexity: O(1).

---

Method 2: Using Set to find the duplicate in linked list.

Implementation

• We will use the Set data structure to store the iterated elements of the linked list.
• Then while moving next in the loop we will keep checking if the element is already present in the set or not.
• If it is present then return it else return -1.

let findDuplicateTwo = (head) => {
    //Use set to store the elm
    let set = new Set();
    
    //Loop the list
    while(head){
      let elm = head.element;
      
      //Check if element is already present or not
      //If it is present then return it
      //Else add it to the set
      if(set.has(elm)){
        return elm;
      }else{
        set.add(elm);
      }
      
      head = head.next;
    }
  
  //Return -1 if no duplicates found
  return -1;
}

Input:
let ll = new LinkedList();
ll.append(1);
ll.append(2);
ll.append(3);
ll.append(4);
ll.append(10);
ll.append(5);
let head = ll.getHead();
console.log(findDuplicate(head));

let ll2 = new LinkedList();
ll2.append(1);
ll2.append(2);
ll2.append(3);
ll2.append(4);
ll2.append(2);
ll2.append(5);
let head2 = ll2.getHead();
console.log(findDuplicate(head2));

Output:
-1
2

Time complexity: O(n).
Space complexity: O(n).