java - 删除错误节点的代码

Question

我正在学习操作节点，并且我的一个测试用例出现问题，并且我的代码似乎没有删除正确的节点。该代码应该删除包含小写字符的节点，但是当测试用例需要 E 时，我会返回 l 。有人可以查看我的代码和测试用例并解释什么是错误的吗？我无法使用静态变量、数组或 Java 集合。

我的代码

public class ListUppercaseExample {

    public static Node<Character> uppercase(Node<Character> head) {
        if (head == null) {
            return null;
        }
        Node<Character> prev = head;
        Node<Character> start = head;

        while (head != null) {
            if (Character.isLowerCase(head.value)) {
                if (Character.isLowerCase(start.value)) {
                    start = head.next;
                    prev = head.next;
                    head = head.next;
                } else {
                    if(head.next == null){
                        return start;
                    }
                    else{
                        prev.next = head.next;
                        head = head.next;
                    }
                }
            } else {
                head = head.next;
            }
        }

        return start;
    }
}

我的节点类

public final class Node<T> {
    public final T value;
    public Node<T> next;

    public Node(T _value) {
        this( _value, null );
    }

    public Node(T _value, Node<T> _next) {
        value = _value;
        next  = _next;
    }

    @Override
    public String toString() {
        return "" + value;
    }
}

测试用例

@Test
public void testDrEvil() {
    @SuppressWarnings("unchecked")
    Node<Character>[] nodes = new Node[] { 
        new Node<Character>( 'd' ), // 0
        new Node<Character>( 'R' ), // 1
        new Node<Character>( 'E' ), // 2
        new Node<Character>( 'v' ), // 3
        new Node<Character>( 'I' ), // 4
        new Node<Character>( 'l', null )
    };

    for (int i = 0; i < nodes.length-1; i++) {
        nodes[ i ].next = nodes[ i+1 ];
    }

    // expected: D -> R
    Node<Character> actual = ListUppercaseExample.uppercase(nodes[0]);
    Node<Character> now = actual;
    assertEquals("", nodes[1], now); // R
    assertEquals("", nodes[2], now.next); // E
    now = now.next;
    assertEquals("", nodes[4], now.next); // I
    now = now.next;
    assertEquals("", null, now.next);
}

Answer 1

您有两个问题:

1. 如果最后一个值是小写的，则不会删除列表中的最后一个值，因为 while 循环中的这一行:

   if(head.next == null){
       return start;
   }
   

   如果 head 的当前值是小写，则无论下一个值是否为 null，您都想跳过它。因此，您可以删除 if 语句的该部分，这样您的代码如下所示:

   if (Character.isLowerCase(start.value)) {
       start = head.next;
       prev = head.next;
       head = head.next;
   } else {
       prev.next = head.next;
       head = head.next;
   }
   

2. 您永远不会更新prev。您需要将 prev 设置为 head在您更改值之前，该字符是大写的头。如果字符是大写，您的 else 语句应该看起来像这样:

   } else {
       prev = head;
       head = head.next;
   }
   

完成这些更改后，您的 while 循环应如下所示:

  while (head != null) {
        if (Character.isLowerCase(head.value)) {
            if (Character.isLowerCase(start.value)) {
                start = head.next;
                prev = head.next;
                head = head.next;
            } else {
                prev.next = head.next;
                head = head.next;
            }
        } else {
            prev = head;
            head = head.next;
        }
    }