链接列表递归removeAll方法

我想定义一个递归方法，它删除单链表中等于目标值的所有实例。我定义了一个remove方法和一个removeAux方法。我该如何改变这种情况，以便如果头部需要移除，头部也会重新分配？以下是我迄今为止：链接列表递归removeAll方法

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

来源

2013-07-01 Chip

这是一个非常糟糕的数据结构和算法不匹配。列表是_linear_，在列表中使用递归没有多大意义。如果它是一个_tree_，那么递归将是适当的。 –

如果您有时间，请查看我的解决方案 –

我宁愿传递到上一参考，当你删除切换之前的下一个像这样

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

检查这个答案graphically linked list可以帮助你思考如何实施它。如果这对训练是好的，但你可以用迭代的方式做。

来源

2013-07-01 23:44:20 nachokk

感谢您的帮助。我稍微改变了我的方法，并在第一次调用removeAux方法时传递removeAux（target，head，head.next）。我尝试这样做：public void removeAux（T target，Node previous，Node current）{ \t \t if（current == null）{ \t \t \t return; \t \t}否则{ \t \t \t如果（target.compareTo（current.data）== 0）{ \t \t \t \t previous.next = current.next; \t \t \t \t current = previous.next; \t \t \t} \t \t \t removeAux（target，previous，current）; \t \t} \t}但现在我得到一个堆栈溢出错误。有任何想法吗？ – Chip

我不明白你发布的所有内容，但在第一次打电话给你应该打电话=实际=头和以前=空...并在如果不比较下..与实际 – nachokk

@ user2506781我编辑和张贴一些代码，希望它帮助我没有测试可能我做了一些错误，但这是idead，这是因为你有一个单一的链表 – nachokk

你可以试着设计你的功能，以便它能像这样工作。

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-01 23:53:07

链接列表递归removeAll方法

回答

相关问题