从链表中删除偶数但不在尾节点工作？

Question

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,2] 结果是[5,3,2] 如何解决这个问题？

Answer 1

的问题是不是与尾节点。问题在于连续的两个节点，无论它们在列表中的什么位置。当前节点即使您刚刚移除指针，也会将指针移动到前一个节点（add）当前节点。对于第二个偶节点，您的add.next = move.next语句将为刚删除的节点更改next。

最简单的办法是只移动add如果节点是连：

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

你可以相当多的通过简化代码摆脱add干脆只是在寻找一个节点提前move：

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

并为您提供一个编程技巧：在尝试诊断问题之前有几个测试用例。我发现基于少量测试用例很容易跳到一个不正确的结论，并且通常扩大范围会使问题更加清晰。这是测试驱动开发和其确实起作用的（许多）原​​因之一。

Answer 2

让我们创建服务节点来连接其他节点。

然后遍历列表，并在一个新的列表复制引用（新节点不创建）：

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; 
} 

假设哪个节点是：

class Node { 
    int data; 
    Node next; 

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