如何通過遞歸添加鏈接列表中的元素？

我做了一個名爲「add」的私有遞歸方法，它應該遞歸添加元素，但它不起作用。我知道java沒有通過引用傳遞，所以如何遞歸添加元素？如果你能告訴我我錯在哪裏，那將是非常棒的。謝謝如何通過遞歸添加鏈接列表中的元素？

public class linkedIt2 { 
private int length = 0; 
private Node head; 


private class Node { 
    Node next; 
    int data; 
    public Node(int data, Node next) { 
     this.data = data; 
     this.next = next; 
    } 

    public Node(int data) { 
     this.data = data; 
     this.next = null; 
    } 
} 


public linkedIt2() { 
    head = null; 
} 

private void add(Node cur, int data) { 
    if (cur != null) { 
     add(cur.next, data); 
    } else { 
     cur = new Node(data, null); 
    } 
} 

public linkedIt2 insert(int data) { 
    add(this.head, data); 
    length++; 
    return this; 
} 
}

來源

2017-07-27 LastGod

「不工作」是什麼意思？ – OldProgrammer

問題是，您不能更改引用。 cur.next永遠不會被更改，因爲引用是通過值調用的。您需要在遞歸調用之前更改cur.next。

您需要了解「按價值調用」的java概念，沒有通過引用調用。引用被轉移爲值，所以更改引用參數本身，原來使用的對象沒有任何反應。也許： http://javadude.com/articles/passbyvalue.htm 使它更清晰。

一個解決方案：類似於您的：

首先，你必須確保小人不爲空。那麼你可以在函數內部訪問cur.next。如果它爲空，則結束遞歸，如果不是，則更深入。

private void add(Node cur, int data) { 
    if (cur.next != null) { 
    add(cur.next, data);  
    } else { 
    cur.next = new Node(data, null); 
    } 
} 

public linkedIt2 insert(int data) { 
    if (this.head == null) { 
    this.head = new Node(data, null); 
    } else { 
    add(this.head, data); 
    } 
    length++; 
    return this; 
}

或者讓Node執行遞歸操作。正如另一種解決方案所述。這更好。

來源

2017-07-27 19:49:00 aschoerk

但是如果我不能引用它，如何在遞歸調用之前更改cur.next？ – LastGod

非常感謝。一個問題，當我通過cur.next時，它是如何發揮作用的，但是當我通過cur時，它不會呢？兩者都沒有被價值調用？ – LastGod

如果您有可用的對象cur的**引用**，則只能操作next。通過引用本身你不能改變，引用指向的內容，你可以改變。如果調用中的對象按值傳遞（如C或C++），情況就不會如此。因爲你只會改變一個副本。這在Java中是不可能的。對象始終作爲引用傳遞。 – aschoerk

你這裏的錯誤是在該行

cur = new Node(data, null);

當調用此它更新本地變量Cur指向一個新的節點，它實際上並沒有使你與調用該方法的變量更新。舉一個簡單的例子

public static void setToFive(int num) { 
    num = 5; 
    System.out.println(num); //Always prints 5 
} 

public static void test() { 
    int test = 3; 
    setToFive(test); 
    System.out.println(test); //Still prints 3 since only num was updated, not test 
}

所以回到原來的問題，並添加元素遞歸你可以做類似

private class Node { 
    //... 
    public void add(int data) { 
     if (next == null) { 
      next = new Node(data, null); 
     } else { 
      next.add(data); 
     } 
}

然後只需撥打head.add（數據），並增加你的長櫃檯。

這個版本更好用，因爲當它創建新節點時，它將類的實例變量設置爲指向它而不是包含在方法中的變量。

來源

2017-07-27 20:00:27

如何通過遞歸添加鏈接列表中的元素？

回答

相關問題