用于在特定位置删除项目的java链表代码

Question

我正在研究单链表，并编写了一个函数，该函数将删除链表中特定位置的元素

我面临的问题是，如果链表中只剩下一个元素，我就无法删除该元素

这是我的密码：

void deleteAtPosN(int position) {

    int i = 1;
    LinkedList temp = head;

    if (position <= 0)
        return;

    while (i < position - 1) {
        temp = temp.next;
        ++i;
    }

    if (temp == null) {
        System.out.println("list is empty");
    } else if (i == position) {
        temp = null;
    } else {
        LinkedList deleteElement = temp.next;
        temp.next = deleteElement.next;
    }
}

Answer 1

您有一个@jrtapsell的迭代解决方案，它跟踪last和current指针。下面是一个递归解决方案，它通过递归调用堆栈跟踪所有last指针。递归解决方案更容易理解和编写，但迭代解决方案比IMO更好，因为它有O（1）额外的内存开销，而不是O（N）

//zero based indexing, assumes position >= 0
public void deleteAtPosN(int position)
{
    head = deleteAtPosNHelper(head, position);
}

//assumes position >= 0
private LinkedList deleteAtPosNHelper(LinkedList current, int position)
{
    if (current == null)
    {
        return null;
    }
    else if (position == 0)
    {
        return current->next;
    }
    else
    {
        current->next = deleteAtPosHelper(current->next,  position);
        return current;
    }
}

Answer 2

为什么你的代码不起作用

当您到达最后一项时，您将temp设置为null，但这不会影响内存中的链表，它只是将您的本地副本更改为null

如何修复

您希望保留对上一个元素的引用，并修改其下一个元素，而不是保留当前项

伪码

fun removeN(index) {
    var current = head
    var last = null
    for (int i = 0; i < index; i++) {
        last = current
        current = current.next
        i++
    }
    if (last == null) {
        // We are at the head of the list
        head = current.next
    } else {
        last.next = current.next
    }
}