title: Interview question: remove duplicates from an unsorted linked list
body: <p>I'm reading <a href="https://rads.stackoverflow.com/amzn/click/com/145157827X" rel="nofollow noreferrer" rel="nofollow noreferrer">Cracking the Coding Interview, Fourth Edition: 150 Programming Interview Questions and Solutions</a> and I'm trying to solve the following question:</p>
  
  <blockquote>
    <p>2.1 Write code to remove duplicates from an unsorted linked list. FOLLOW
    UP: How would you solve this problem if
    a temporary buffer is not allowed?</p>
  </blockquote>
  
  <p>I'm solving it in C#, so I made my own <code>Node</code> class:</p>
  
  <pre><code>public class Node&lt;T&gt; where T : class
  {
      public Node&lt;T&gt; Next { get; set; }
      public T Value { get; set; }
  
      public Node(T value)
      {
          Next = null;
          Value = value;
      }
  }
  </code></pre>
  
  <p>My solution is to iterate through the list, then for each node to iterated through the remainder of the list and remove any duplicates (note that I haven't actually compiled or tested this, as instructed by the book):</p>
  
  <pre><code>public void RemoveDuplicates(Node&lt;T&gt; head)
  {
      // Iterate through the list
      Node&lt;T&gt; iter = head;
      while(iter != null)
      {
          // Iterate to the remaining nodes in the list
          Node&lt;T&gt; current = iter;
          while(current!= null &amp;&amp; current.Next != null)
          {
              if(iter.Value == current.Next.Value)
              {
                  current.Next = current.Next.Next;
              }
  
              current = current.Next;
          }    
  
          iter = iter.Next;
      }
  }
  </code></pre>
  
  <p>Here is the solution from the book (the author wrote it in java):</p>
  
  <blockquote>
    <p>Without a buffer, we can iterate with
    two pointers: “current” does a normal
    iteration, while “runner” iterates
    through all prior nodes to check for
    dups. Runner will only see one dup per
    node, because if there were multiple
    duplicates they would have been
    removed already.</p>
  </blockquote>
  
  <pre><code>public static void deleteDups2(LinkedListNode head) 
  {
      if (head == null) return;
  
      LinkedListNode previous = head;
      LinkedListNode current = previous.next;
  
      while (current != null) 
      {
          LinkedListNode runner = head;
  
          while (runner != current) { // Check for earlier dups
              if (runner.data == current.data) 
              {
                  LinkedListNode tmp = current.next; // remove current
                  previous.next = tmp;
                  current = tmp; // update current to next node
                  break; // all other dups have already been removed
              }
              runner = runner.next;
          }
          if (runner == current) { // current not updated - update now
              previous = current;
              current = current.next;
          }
      }
  }
  </code></pre>
  
  <p>So my solution always looks for duplicates for the current node to the end, while their solution looks for duplicates from the head to the current node. I feel like both solutions would suffer performance issues depending on how many duplicates there are in the list and how they're distributed (density and position). But in general: is my answer nearly as good as the one in the book or is it significantly worse?</p>