遞歸地從鏈表中刪除節點

Question

給定一個鏈表的頭部和作爲參數搜索的int，我需要一個方法來刪除列表中第一次出現這個數字，然後返回修改後的列表。但是我無法修改原始列表。我知道如何從列表中刪除節點，但我不知道如何保持原始列表完整無缺，因爲這必須遞歸地完成。下面是方法 **最初M是原始列表。我不知道它會再次調用該方法後仍然是同一個列表...？

MyList removeNumber(MyList m, int removee){ 

Answer 1

//This function will always return a new list with 'remove' removed 
MyList removeNumber(MyList m, int remove){ 
//if m is empty List, return an empty list 

//if head is not the int to remove, return a New list from 
// head concat removeNumber(m.next,remove) 
//else return removeNumber(m.next,remove) 
} 

Answer 2

我認爲它缺乏信息。但是我假設爲鏈表一個非常傳統的實現，例如：

class MyList { 

    MyList prev; 
    MyList next; 
    int data; 

    static MyList removeNumber(MyList m,int removee) { 

    if(m == null) return null; // already empty 

    if(m.data == removee) { // m already is the node to throw away 

     if(m.prev != null)// relink 
     m.prev.next = m.next; 

     if(m.next != null)// relink 
     m.next.prev = m.prev; 

     return m.prev; 
    } 
    // if this node isn't the one yet, keep looking for 
    return removeNumber(m.next,removee); 
    } 
} 

有很多不同的方法來做到這一點，但你必須爲了提供更多信息，讓我們來點你正確的文學。

Answer 3

這個想法是生成的結構將是一個「Y」：雙頭列表（實際上是一個簡單的圖）。

Y的一個分支是原始列表。另一個是你的新列表與刪除節點。 Y的垂直軸是你移除的元素之後的東西。這兩個列表都很常見。這裏有一些ascii藝術，Y轉身顯示1到5的列表，其中3被刪除。

 new -> 1 -> 2 ------\ 
          v 
original -> 1 -> 2 -> 3 -> 4 -> 5 -> null 

遞歸地思考是關於定義一個問題的小本身加上一個固定的工作。你需要一個基本案例（或者幾個）。

鏈表本身是一種遞歸結構：

列表爲空或者是由它的「下一個」參考到列表鏈接的元件。

注意這個定義了一個使用較小列表的列表。基本情況是空的列表。固定位是元素。

閱讀這個定義幾次，然後看看它是如何轉換的代碼：

class MyList { 
    int value; // the element at the head of this list 
    MyList next; // the rest of the list 

    MyList(int value, MyList next) { 
    this.value = value; 
    this.next = next; 
    } 
} 

基本情況「空單」僅僅是一個參考null。使用相同模式遞歸表示的元素移除問題變爲：

移除元素的列表的副本是a）在要移除的元素是頭或b）當前節點的副本，然後複製列表的其餘部分，並刪除所需的元素。

在這裏，我定義了「刪除一個元素的列表的副本」，使用同一個東西的較小版本。情況a）是基本情況。固定位是而不是removee。

當然還有另一個基本情況：如果列表爲空，則找不到removee。這是一個錯誤。

在代碼中把這樣的：

MyList removeNumber(MyList m, int removee) { 
    if (m == null) throw new RuntimeException("removee not found"); 
    if (m.value == removee) return m.next; 
    return new MyList(m.value, removeNumber(m.next, removee)); 
} 

把使用看起來像這樣的功能：

MyList originalList = ... // list of 1 to 5. 
MyList newListWith3removed = removeNumber(originalList, 3); 

System.out.println("Original list:"); 
for (MyList p : originalList) System.out.println(p.value); 
System.out.println("With 3 removed:"); 
for (MyList p : newListWith3removed) System.out.println(p.value); 

輸出如下預期：在第一個列表，一月一日至五日，第二，2,4,5。即第一個列表不變。