尋找k到第一個單向鏈表的最後一個元素

我有兩個遞歸解決方案「k到第一個單向鏈表的最後一個元素」的問題在Java中：尋找k到第一個單向鏈表的最後一個元素

解決方案1：

public static Node nthToLast(Node head, int k , int i){ 
    if (head == null) return null; 
    Node n = nthToLast(head.next, k, i); 
    i = i + 1; 

    if (i == k) return head; 

    return n; 
}

解決方案2：

public class IntWrapper { 
    public int value = 0; 
} 
public static Node nthToLast(Node head, int k, IntWrapper i){ 
    if (head == null) return null; 
    Node n = nthToLast(head.next, k, i); 
    i.value = i.value + 1; 

    if (i.value == k) return head; 

    return n; 
}

第一溶液返回null，而第二個解決方案完美運作。第一個解決方案按值通過k，而第二個解決方案將int值包裝到一個類中並通過它。

我有兩個問題：

爲什麼沒有用Java開發的第一個解決方案？爲什麼通過每個方法調用中的局部變量i傳遞的值與傳遞參考版本不一樣？
的Integer類的Java包int，但在第一個解決方案替換int到Integer不能正常工作。爲什麼？

來源

2013-12-23 user2925218

在您的第一個解決方案中，我沒有初始化 – Vorsprung

@Vorsprung我相信「我」是一個方法參數，儘管我不知道最初的調用是什麼樣的。 – aquaraga

初始調用如下所示：first solution：Node n = nthToLast（testRootNode，2，0）;第二種解決方案：節點n = nthToLast（testRootNode，2，new IntWrapper（））; – user2925218

在解決方案2中，您使用IntWrapper來記住跨遞歸調用的值。在這裏，IntWrapper就像一個全局值。

如果使用本地變量（如基本整數），則不能保留跨調用增加的（i = i + 1）值。因此，語句if (i == k) return head;永遠不會成爲真正的，除非也許如果k = 1

最有趣的是，你不能使用Integer因爲Java包裝類的性質不變。在你做i = i + 1的那一刻，一個新的對象被創建（LHS），舊的（RHS）被丟棄/垃圾收集。

來源

2013-12-23 09:58:39 aquaraga

它不需要做可變/不可變，而是應用於盒裝類型時'+'的語義。 – newacct

如果IntWrapper「充當全局值」，那麼是否可以將IntWrapper變成全局變量呢？這樣做有沒有優勢/劣勢？ – randomUser47534

是的，你可以有一個全局的IntWrapper實例;在這種情況下，您不需要對其進行參數化。從代碼中的任何位置獲得全球價值非常容易 - 這種易於轉化的最大缺點是：很難推斷其狀態。至於所有的事情，這取決於你是否選擇將其視爲劣勢。例如 - 本質上算法的問題域可能不認爲這是一個缺點，而業務建模面向對象的解決方案可能。 – aquaraga

在你的解決方案1中，你應該在遞歸調用方法之前遞增i。這個版本應該工作：

public static Node nthToLast(Node head, int k , int i) { 
    // checks empty case 
    if (head == null) { return null; } 

    // checks if current node is the solution 
    if (i == k) { return head; } 

    // else checks next node 
    return nthToLast(head.next, k, i+1); 
}

來源

2013-12-23 10:27:34 polypiel

1. 因爲每次你在i變量傳遞相同的值第一個解決方案是行不通的。如果你通過Node n = nthToLast (head.next, k, i)這條線移動i = i + 1這條線，一切都應該沒有問題。
2. Integer類是不可變的，因此表現得像一個正常的int。這就是爲什麼如果您在第一個解決方案中使用Integer將無法正常工作。正如我在上面提到的，您可以替換代碼行，第一個解決方案使用Integer。
第二種解決方案的工作原理是，計數器增量的方式不會覆蓋對計數對象的引用。

來源

2013-12-23 10:49:10

尋找k到第一個單向鏈表的最後一個元素

回答

相關問題