程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> JAVA編程 >> 關於JAVA >> 編碼完成從無序鏈表中移除反復項(C和JAVA實例)

編碼完成從無序鏈表中移除反復項(C和JAVA實例)

編輯:關於JAVA

編碼完成從無序鏈表中移除反復項(C和JAVA實例)。本站提示廣大學習愛好者:(編碼完成從無序鏈表中移除反復項(C和JAVA實例))文章只能為提供參考,不一定能成為您想要的結果。以下是編碼完成從無序鏈表中移除反復項(C和JAVA實例)正文


假如不克不及應用暫時緩存,你怎樣編碼完成?

辦法一:不應用額定的存儲空間,直接在原始鏈表長進行操作。起首用一個指針指向鏈表頭節點開端,然後遍歷厥後面的節點,將與該指針所指節點數據雷同的節點刪除。然後將該指針後移一名,持續上述操作。直到該指針移到鏈表。

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved