从单链表中删除两个给定位置之间的节点？

我正在教授自己的数据结构，并关注有关此主题的Java书籍。目前我正在学习链接列表实现。我一直在努力如何编写一个采用“startPos”和“endPos”的方法，并相应地删除节点。我正在验证“startPos”和“endPos”以捕获无效的位置输入。我已经谷歌搜索方向，但还没有遇到任何在线例子，可以帮助我走这个逻辑。我非常感谢您的任何指导。谢谢。从单链表中删除两个给定位置之间的节点？

class Node{ 

    public Object data; 
    public Node next; 

}

删除节点方法

public void deleteNodes(int startPos, int endPos){   
     Node node = _nHead; 
     int counter = 0; 

    if(startPos < 1 || startPos > getSize()) 
     return; 

    if(endPos < 1 || endPos > getSize()) 
     return; 


    while(node != null){ 

    node = node.next; 
    ++counter; 
    } 
}

GET SIZE

public int getSize(){ 

    int counter = 0; 

    for(Node node = _nHead; node != null; node = node.next) 
    ++counter; 
    return counter; 
}

来源

2014-04-23 Combustion007

要删除一个单向链表在两个节点之间的所有节点是不是超级难。

您需要两个占位符。您将浏览链接列表，直到找到您的起始节点，并将其中一个占位符设置为与之相同。然后，将第二个占位符移动到链表的其余部分，直到找到第二个节点。设置你的第一个节点的 - >下一个参数等于第二个节点，并且你已经有效地移除了它们之间的所有内容。

为了正确清理，您应该跟踪第一个节点之后的下一个节点，并释放所有已从内存中删除的节点，但这在C中比Java更重要。

对于双向链表，该方法是类似的，除非您还必须将第二个节点的前一个设置为第一个节点。

作为一个例子：

public void deleteNodes(int startPos, int endPos){   
    Node node = _nHead; 
    Node start; 
    Node end; 

    int counter = 0; 

    if(startPos < 1 || startPos > getSize()) 
     return; 

    if(endPos < 1 || endPos > getSize()) 
     return; 

    if (endPos < startPos) 
    { 
     int placeholder = startPos; 
     startPos = endPos; 
     endPos = placeholder; // switches end and start if start is greater than end 
    } 

    if (endPos == startPos) 
     return; // if they are equal we aren't deleting anything; 


    while(node != null) 
    { 
     if (counter == startPos) 
      start = node; 

     if (counter == endPos) 
      end = node; 

     node = node.next; 
     counter++; 
    } 

    if (start != NULL && end != NULL) 
    { 
     start.next = end; 
    } 
}

来源

2014-04-23 20:10:20

只需将必须的节点的下一指针设定在移除范围的开始到在移除范围的端部的节点。由于在删除范围内没有对节点的引用，因此Java的垃圾回收应该将其清除。

来源

2014-04-23 20:14:07 Craig

从单链表中删除两个给定位置之间的节点？

回答

相关问题