0

我正在尝试定义一个递归方法，该方法删除单链表中等于目标值的所有实例。我定义了一个 remove 方法和一个随附的 removeAux 方法。我怎样才能改变它，以便如果需要移除头部，头部也会被重新分配？这是我到目前为止所拥有的：

public class LinkedList<T extends Comparable<T>> {

private class Node {
    private T data;
    private Node next;

    private Node(T data) {
        this.data = data;
        next = null;
    }
}

private Node head;

public LinkedList() {
    head = null;
}

public void remove(T target) {
    if (head == null) {
        return;
    }

    while (target.compareTo(head.data) == 0) {
        head = head.next;
    }

    removeAux(target, head, null);
}

public void removeAux(T target, Node current, Node previous) {
    if (target.compareTo(current.data) == 0) {
        if (previous == null) {
            head = current.next;
        } else {
            previous.next = current.next;
        }
        current = current.next;
        removeAux(target, current, previous); // previous doesn't change

    } else {
        removeAux(target, current.next, current);
    }
}
4

2 回答 2

0

您可以尝试调整您的功能，使其像这样工作。

 head = removeAux(target, head); // returns new head

我没有从 Coursera 的算法课程中学到的一个巧妙的技巧。

其余代码如下。

public void removeAux(T target, Node current) {
  //case base
   if(current == null)
           return null;

   current.next = removeAux(target, current.next);

   return target.compareTo(current.data) == 0? current.next: current; // the actual deleting happens here
}
于 2013-07-01T23:53:07.863 回答
0

当您删除以将上一个切换到下一个时，我更喜欢传递对上一个的引用，如下所示

public void remove(T target){
   removeAux(target,head, null);
}


public void removeAux(T target, Node current, Node previous) {
      //case base
       if(current == null)
               return;

    if (target.compareTo(current.data) == 0) {

        if (previous == null) {
          // is the head
            head = current.next;
        } else {
            //is not the head
            previous.next = current.next;
        }
        current = current.next;
        removeAux(target, current, previous); // previous doesn't change

    } else {
        removeAux(target, current.next, current);
    }
}

检查这个答案图形链接列表可能会帮助您思考如何实现它。如果这对培训很好，但您可以以迭代的方式进行。

于 2013-07-01T23:44:20.143 回答