title: C: Remove duplicates from unsorted linked list
body: <p>I have been working on this problem for more hours than I'd like to admit now and it's driving me nuts! Given a simple linked list, say one that stores an integer (<code>data</code>) only in addition to a pointer to the next node (<code>next</code>), I would like an algorithm that removes duplicates without sorting or relying on helper functions.</p>
  
  <p>Previous questions have been asked about unsorted linked lists in Java which take advantage of helper functions that Java offers. This is strictly pertinent to C without the use of helper functions.</p>
  
  <p>I have tinkered around with code and have got this to work for some cases, but not all. Here is a complete, verifiable example -- I've include a <code>push()</code> function to create a linked list and a <code>main()</code> with test cases, but the logic that my question pertains to is in <code>removeDuplicates()</code> alone:</p>
  
  <pre><code>#include &lt;stdlib.h&gt;
  #include &lt;stdio.h&gt;
  
  struct node {
      int data;
      struct node *next; 
  };
  
  void push(struct node **headRef, int data) {
      struct node *newNode = malloc(sizeof(struct node));
      newNode-&gt;data = data;
      newNode-&gt;next = *headRef;
      *headRef = newNode;
  }
  
  void removeDuplicates(struct node **head) {
          struct node *currentNode = *head; //The node we compare other nodes against
      struct node *runningNode = (*head)-&gt;next; //The node we are comparing to
      struct node *runningNodePrev = *head; //The node before the node we are comparing to
      struct node *runningNodeNext = (*head)-&gt;next-&gt;next; // The node after the node we are comparing to
      int count = -1;
      while (currentNode-&gt;next != NULL) { //Ensure we are not looking at the last node -- cannot have comparisons past this node
          count++;
          if (count) {
              //'Base Position'
              currentNode = currentNode-&gt;next;
              runningNodePrev = currentNode;
              runningNode = currentNode-&gt;next;
              runningNodeNext = runningNode-&gt;next;
          }
          printf("\nChecking for a match with  %d ... \n", currentNode-&gt;data);
          while (runningNode != NULL) { //Compare each node in the list until we reach the end of the list
              printf("Inspecting next adjacent node ... \n");
              if (runningNode-&gt;data == currentNode-&gt;data) {//If a duplicate is found
                  printf("Found match ... ");
  
                  //Ensure link is maintained before removing duplicate node
                  if (currentNode == runningNodePrev)
                      currentNode-&gt;next = runningNodeNext;
                  runningNodePrev-&gt;next = runningNodeNext; 
  
                  free(runningNode);//Delete duplicate node
                  printf("Deleted duplicate.\n");
              }
              runningNode = runningNodeNext;//Continue searching for duplicates at the first unchecked node
              runningNodeNext = runningNodeNext-&gt;next;//Move running node leader up the list.     
          }
      }
  }
  
  int main(void) {
      struct node *t1 = NULL;
      struct node *t2 = NULL;
      struct node *t4 = NULL;
      struct node *t5 = NULL;
      push(&amp;t1, 1);
      push(&amp;t1, 1);
      push(&amp;t1, 1);
      push(&amp;t1, 1);
      push(&amp;t2, 6);
      push(&amp;t2, 1);
      push(&amp;t2, 2);
      push(&amp;t2, 3);
      push(&amp;t2, 4);
      push(&amp;t2, 5);
      push(&amp;t2, 6);
      push(&amp;t4, 4);
      push(&amp;t4, 2);
      push(&amp;t4, 3);
      push(&amp;t4, 2);
      push(&amp;t4, 1);
      push(&amp;t5, 0);
      push(&amp;t5, 0);
      push(&amp;t5, 1);
      printf("Testing removeDuplicates()...\n");
      printf("Case 1: Calling removeDuplicates({1,0,0}).\n");
      printf("Expected result: { 1 0 }\n");
      printf("Actual result:   { ");
      removeDuplicates(&amp;t5);
      ptr = t5;
      while (ptr != NULL) { 
          printf("%d ", ptr-&gt;data);
          ptr = ptr-&gt;next;
      }
      printf("}\n");
      printf("Case 2: Calling removeDuplicates({1,2,3,2,4}).\n");
      printf("Expected result: { 1 2 3 4 }\n");
      printf("Actual result:   { ");
      removeDuplicates(&amp;t4);
      ptr = t4;
      while (ptr != NULL) {
          printf("%d ", ptr-&gt;data);
          ptr = ptr-&gt;next;
      }
      printf("}\n");
      printf("Case 3: Calling removeDuplicates({6,5,4,3,2,1,6}).\n");
      printf("Expected result: { 6 5 4 3 2 1 }\n");
      printf("Actual result:   { ");
      removeDuplicates(&amp;t2);
      ptr = t2;
      while (ptr != NULL) {
          printf("%d ", ptr-&gt;data);
          ptr = ptr-&gt;next;
      }
      printf("}\n");
      printf("Case 4: Calling removeDuplicates({1,1,1,1}).\n");
      printf("Expected result: { 1 }\n");
      printf("Actual result:   { ");
      removeDuplicates(&amp;t1);
      ptr = t1;
      while (ptr != NULL) {
          printf("%d ", ptr-&gt;data);
          ptr = ptr-&gt;next;
      }
      printf("}\n");
  }
  </code></pre>
  
  <p>I've also included a picture that describes the logic if it is unclear what I'm doing: <a href="https://imgur.com/DbnBOq2" rel="nofollow noreferrer">http://imgur.com/DbnBOq2</a></p>