java - 破坏性地删除链表中的所有其他元素

Question

我成功地能够以非破坏性方式从链接列表中删除所有其他元素(通过返回新的链接列表)。这是该函数:

public static Link<Integer> everyOther(Link<Integer> link){
    if(link == null) return null; 
    if(link.next == null) return link;
    return new Link(link.data, everyOther(link.next.next)); 
}

对于输入列表 1, 2, 3, 4，它成功返回 1, 3。

但是我现在尝试破坏性地执行此操作(使用 void 返回类型)，但遇到了麻烦。这是我迄今为止的尝试:

public static void everyOtherDestructive(Link<Integer> link){
    if(link == null) return; 
    if(link.next == null) return;
    if(link.next.next != null){
        link.next = link.next.next;
        everyOtherDestructive(link.next); 

    }               
}

这仅适用于奇数长度的列表，但不适用于偶数长度的列表。 1, 2, 3, 4 的链表应该更改为 1, 3。但是我得到的是 1, 3, 4。

任何人都可以帮助我理解为什么它没有像应该那样跳过最后一个元素？

Answer 1

这是因为，当您位于 3 时，您什么也不做(因为 link.next.next 为 null)。

此时，您应该将 link.next 设置为 null。当您删除整个 if 语句时，这会自动实现。

public static void everyOtherDestructive(Link<Integer> link){
    if(link == null) return; 
    if(link.next == null) return;
    link.next = link.next.next;
    everyOtherDestructive(link.next); 
}