Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Problems: Linked Lists

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

Remove duplicates

Write code to remove duplicates from an unsorted linked list. Could you also solved this without using a temporary buffer?

👉 Link here to the repo to solve the problem

imagen

👌 Tips

Have you tried a hash table? You should be able to do this in a single pass of the linked list.

Without extra space, you’ll need a (N2) time. Try using two pointers, where the second one searches ahead of the first one.

👊 Solution 1

I wrote a fairly easy solution in which we add every unique node data onto a HashSet, every time we see that it already exists in this set we just skip to the next node - hence removing the duplicate. Note that at the very end we have to also do it for the very last node in the List:

public static void removeDupplicates(SingleLinkedListNode head) {
    SingleLinkedListNode n = head;
    HashSet<Integer> a = new HashSet<>();

    while (n.next != null) {
        int i = n.data;
        if (!a.contains(i)) a.add(i);

        if(a.contains(n.next.data) && n.next.next != null) {
            n.next = n.next.next;
        }

        if(a.contains(n.next.data)) {
            n.next = null;
        } else {
            n = n.next;
        }
    }
}


Question borrowed from “Cracking the coding interview”

Last updated on 3/6/2020
← Valid ParenthesisKth to last node →
  • 👉 Link here to the repo to solve the problem
  • 👌 Tips
  • 👊 Solution 1
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr