如果不能使用臨時緩存，你怎麼編碼實現？
代碼如下：
方法一：不使用額外的存儲空間，直接在原始鏈表上進行操作。首先用一個指針指向鏈表頭節點開始，然後遍歷其後面的節點，將與該指針所指節點數據相同的節點刪除。然後將該指針後移一位，繼續上述操作。直到該指針移到鏈表。
void delete_duplicate1(node* head){
node*pPos=head->next;
node*p,*q;
while(pPos!=NULL){//用pPos指針來指示當前移動到什麼位置了
p=pPos;
q=pPos->next;
while(q!=NULL){//遍歷pPos後面的所有節點，找出節點值與pPos所指節點相同的節點，將其刪除
if(pPos->data==q->data){
node*pDel=q;
p->next=q->next;
q=p->next;
free(pDel);
}
else{
p=q;
q=q->next;
}
}
pPos=pPos->next;
}
}
方法二：如果允許使用額外的空間，則能通過空間換時間，來降低算法的復制度。可以使用hash表來完成，既然是面試題，我們這裡可以暫時先不考慮使用hash可能帶來的一些問題，先假設它是完美的。即假設它能將任意整數hash到一定范圍，不會出現負數下標，不會出現hash沖突等。
代碼如下：
void delete_duplicate2(node* head)
{
node*p=head->next;
node*q=p->next;
memset(hash,0,sizeof(hash));
hash[p->data]=1;//置為1，表示該數已經出現過
while(q!=NULL){
if(hash[q->data]!=0){
node*pDel=q;
p->next=q->next;
q=p->next;
free(pDel);
}
else{
hash[q->data]=1;//置為1，表示該數已經出現過
p=q;
q=q->next;
}
}
}
JAVA參考代碼：
代碼如下：
public static void deleteDups(LinkedListNode n) {
Hashtable table = new Hashtable();
LinkedListNode previous = null;
while (n != null) {
if (table.containsKey(n.data)) previous.next = n.next;
else {
table.put(n.data, true);
previous = n;
}
n = n.next;
}
}
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;
}
}
}
