快捷導(dǎo)航

編碼實(shí)現(xiàn)從無序鏈表中移除重復(fù)項(xiàng)(C和JAVA實(shí)例)

更新時(shí)間：2013年10月30日 10:16:26 作者：

如果不能使用臨時(shí)緩存，你怎么實(shí)現(xiàn)無序鏈表中移除重復(fù)項(xiàng)(？C和JAVA實(shí)例無序鏈表中移除重復(fù)項(xiàng)。

如果不能使用臨時(shí)緩存，你怎么編碼實(shí)現(xiàn)？

方法一：不使用額外的存儲(chǔ)空間，直接在原始鏈表上進(jìn)行操作。首先用一個(gè)指針指向鏈表頭節(jié)點(diǎn)開始，然后遍歷其后面的節(jié)點(diǎn)，將與該指針?biāo)腹?jié)點(diǎn)數(shù)據(jù)相同的節(jié)點(diǎn)刪除。然后將該指針后移一位，繼續(xù)上述操作。直到該指針移到鏈表。

void delete_duplicate1(node* head){
    node*pPos=head->next;
    node*p,*q;
    while(pPos!=NULL){//用pPos指針來指示當(dāng)前移動(dòng)到什么位置了
        p=pPos;
       q=pPos->next;
       while(q!=NULL){//遍歷pPos后面的所有節(jié)點(diǎn)，找出節(jié)點(diǎn)值與pPos所指節(jié)點(diǎn)相同的節(jié)點(diǎn)，將其刪除
            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;
        }
}

方法二：如果允許使用額外的空間，則能通過空間換時(shí)間，來降低算法的復(fù)制度?？梢允褂胔ash表來完成，既然是面試題，我們這里可以暫時(shí)先不考慮使用hash可能帶來的一些問題，先假設(shè)它是完美的。即假設(shè)它能將任意整數(shù)hash到一定范圍，不會(huì)出現(xiàn)負(fù)數(shù)下標(biāo)，不會(huì)出現(xiàn)hash沖突等。

復(fù)制代碼代碼如下:

void delete_duplicate2(node* head)
{
    node*p=head->next;
    node*q=p->next;
    memset(hash,0,sizeof(hash));
    hash[p->data]=1;//置為1，表示該數(shù)已經(jīng)出現(xiàn)過
    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，表示該數(shù)已經(jīng)出現(xiàn)過
            p=q;
            q=q->next;
            }
        }
}

JAVA參考代碼：

復(fù)制代碼代碼如下:

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;
      }
    }
 }