Removing duplicates from LL and keeping only last appearance

help
,
1

You are given an unsorted singly linked list that may contain duplicate elements. You are supposed to remove all duplicate elements from the linked list and keep only the last appearance of elements.

#include<bits/stdc++.h>

        class Node
        {
        public:
	        int data;
	        Node *next;
	        Node(int data)
	        {
		        this->data = data;
		        this->next = NULL;
	        }
        };

Node *lastAppearance(Node *head){
    // Write your code here.
    if(head == NULL) return NULL;
	Node* prev = NULL;
    Node* curr = head;
    Node* next = head->next;
    while(curr != NULL){
        next =curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    Node* newprev = NULL;
    Node* newHead = prev;
    map<int, int> m;
    while(newHead != NULL){
        if(m[newHead->data] == 0){
            m[newHead->data]++;
            newprev = newHead;
            newHead = newHead->next;
        }else{
            newprev->next = newHead->next;
            newHead = newHead->next;
        }
    }
    curr = prev;
    next = curr->next;
    prev = NULL;
    while(curr != NULL){
        next =curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

My Approach:
I reversed the linked list and then removed duplicates using hashing. At last, I reversed the list again. But I am getting TLE for this, N<=5X1e5

2

@cubefreak777 please help me in this

3

problem link?

4

Question

5 
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def lastAppearance(head):

  li = [] ## list of nodes
  while head:
      nxt = head.next
      head.next = None
      li.append(head)
      head = nxt
  
  seen = {}
  ch, ct = None, None
  for node in li[-1::-1]:
      if node.data in seen:
          continue
      if ct == None:
          ct = node
          ch = node
      else:
          node.next = ch
          ch = node
      seen[node.data] = True
  return ch

My Code in Python seems to work though. Same Approach mostly as u stated

6

Yeah that is what I am saying that I don’t find any flaw in my approach but my code didn’t seem to work. If you are a little bit familiar with C++, then give it a try as I reviewed it many times but I am not able to find the flaw

7

Answer is correct. Try to do this in 2N times. I think 3N is hitting the time limit

8
Use unordered_map 
#include<bits/stdc++.h>

Node *lastAppearance(Node *head){
    // Write your code here.
    if(head == NULL) return NULL;
	Node* prev = NULL;
    Node* curr = head;
    Node* next = head->next;
    while(curr != NULL){
        next =curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    Node* newprev = NULL;
    Node* newHead = prev;
    unordered_map<int, int> m;
    while(newHead != NULL){
        if(m[newHead->data] == 0){
            m[newHead->data]++;
            newprev = newHead;
            newHead = newHead->next;
        }else{
            newprev->next = newHead->next;
            newHead = newHead->next;
        }
    }
    curr = prev;
    next = curr->next;
    prev = NULL;
    while(curr != NULL){
        next =curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}
1 Like
9

Ohh Yeah map is a red black tree and not a hash map. Didn’t pay attention there.