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

Question

我正在自学数据结构并遵循有关该主题的 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;
  }
}   

获取尺寸

public int getSize(){

    int counter = 0;

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

Answer 1

删除单链表上两个节点之间的所有节点并不难。

您需要两个占位符。您在链表中移动，直到找到起始节点，并将占位符之一设置为等于它。然后，将第二个占位符移动到链表的其余部分，直到找到第二个节点。将第一个节点的 -> next 参数设置为等于第二个节点，这样您就有效地删除了中间的所有内容。

为了正确清理，您应该跟踪第一个节点之后的下一个节点，并释放从内存中删除的所有节点，但这在 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;
    }
}