代码之家 › 专栏 › 技术社区 › Django

从链接列表中删除偶数在尾部节点不起作用?

nodelist linked-list data-structures java

0

Django · 技术社区 · 11 年前

void deleteEven() {
        boolean con = false;
        Node add;
        Node move;
        move = head;
        if (move.data % 2 == 0) {
            head = move.next;
            con = true;
        }
        add = move;
        move = move.next;
        while (move != null) {
            if (move.data % 2 == 0 ) {
                add.next = move.next;
                con = true;
            }
            add = move;
            move = move.next;
        }
        if (!con)
            System.out.println("No even numbers in list");
    }

它适用于除尾部之外的每个节点。如果链接列表为[5,4,3,2] 结果是[5,3,2] 如何修复?

2 回复 | 直到 11 年前

1

sprinter 11 年前

问题不在于尾部节点。问题是一行中有两个偶数节点,而不管它们在列表中的位置。当当前节点为偶数时,您将指针移动到上一个节点( add )即使您刚刚删除了当前节点。对于第二个偶数节点 add.next = move.next 语句更改 next 对于刚刚删除的节点。

最简单的解决方案是只移动 添加 如果节点不是偶数:

if (move.data % 2 == 1) {
    add.next = move.next;
    con = true;
} else {
    add = move.next;
}

您可以通过取消 添加 只需提前一个节点 move :

while (move.next != null) {
    if (move.next.data % 2 == 0) {
        move.next = move.next.next;
        con = true;
    } else {
        move = move.next;
    }
}

还有一个编程提示:在尝试诊断问题之前,先进行几个测试用例。我发现,基于少量的测试用例很容易得出错误的结论,而且经常扩大范围会使问题更清楚。这是测试驱动开发工作良好的原因之一。

2

0

Svichkarev Anatoly stinepike 11 年前

让我们创建用于连接其他节点的服务节点。

然后循环列表并复制新列表中的引用(不创建新节点):

void deleteEven() {
    Node tmpHead = new Node(0, null);
    Node tmpCopy = tmpHead;
    Node tmp = head;
    while (tmp != null) {
        if (tmp.data % 2 == 1) {
            tmpCopy.next = tmp;
            tmpCopy = tmpCopy.next;
        }
        tmp = tmp.next;
    }
    tmpCopy.next = null;
    head = tmpHead.next;
}

假设Node是:

class Node {
    int data;
    Node next;

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