链表问题无序链表中删除重复节点

Question: Write code to remove duplicates from an unsorted linked list.( from Cracking the coding interview)

链表使用以下结构

1 struct LinkListNode
2 {
3     int key;
4     LinkListNode *next;
5 };

解法一：使用hash，即要求缓冲区。遍历链表，若不含该节点值，则加入hash表，否则跳过该节点。

C++好像没有直接的hashtable~~实现有待学习！

解法二：不使用buffer，使用两个指针，分别指向当前节点pCur和其前一节点pPre，遍历pCur过程中，对每一个pCur设置一个指针runner从head开始检查是否有和当前节点重复的节点，有则跳过并break(到当前节点最多有一个重复的，因为若链表中重复节点有多于1个，会在前面的节点中删除)，无重复则更新pPre 和pCur。

实现如下code:

 1 void deleteDups(LinkListNode *head)
 2 {
 3     LinkListNode *pPre = head;
 4     LinkListNode *pCur = pPre->next;
 5     while (pCur != NULL)
 6     {
 7         LinkListNode *runner = head;
 8         //检查之前的节点是否和当前重复，且只有一个（多的会在遍历之前的节点时删除）
 9         while (runner != pCur)
10         {
11             if (runner->key == pCur->key)
12             {//跳过当前节点
13                 LinkListNode *tmp = pCur->next;
14                 pPre->next = tmp;
15                 pCur = tmp;
16                 break;
17             }
18             runner = runner->next;
19         }
20         //若当前没重复，则更新pPre 和pCur
21         if (runner == pCur)
22         {
23             pPre = pCur;
24             pCur = pPre->next;
25         }
26     }
27 }