java - 在链表中添加元素并按键排序

Question

我在下面编写了一段代码，用于在链接列表中按排序顺序添加元素及其键。但它不会根据键对它们进行排序，并且仅按插入顺序添加。看来我错过了一些东西。

public void insert(int key, int value)
{
    Link pcurrent = pfirst;
    Link newLink = new Link(key, value);
    if(pcurrent != null)
    {
        while(pcurrent.key <= newLink.key && pcurrent.next != null)
        {
            pcurrent = pcurrent.next;
        }
        Link temp = pcurrent.next ;
        pcurrent.next = newLink;
        newLink.next = temp;
    }
    else
    {
        newLink.next = pfirst;
        pfirst = newLink;
    }
    System.out.println("After inserting element in the linked List");
    display();
}

Answer 1

让我们通过一个示例来了解如何修复您的代码。由于这些值不是算法的一部分，因此我将在下面的讨论中忽略它们。首先，假设我们已经有一个包含以下键的列表:

5 -> 42 -> 69

现在让我们分析调用list.insert(53, x);，它应该插入一个(键，值)对作为列表中的第三个元素。

从列表的开头开始。

    Link pcurrent = pfirst;

创建一个新节点。

    Link newLink = new Link(key, value);

确保我们不在列表的末尾。

    if(pcurrent != null)
    {

单步遍历列表以找到应插入新链接的节点。请注意，我们必须非常小心地处理此循环。这里很容易出现相差一的错误。

        while(pcurrent.key <= newLink.key && pcurrent.next != null)
        {
            pcurrent = pcurrent.next;
        }

请注意，我们必须非常小心地处理这个循环。这里很容易出现相差一的错误。那么让我们更仔细地分析一下。

在我们的示例中，pcurrent.key 以值 5 开头，该值小于我们要插入的 53。此外，pcurrent.next 不是 null。因此，我们转到下一个 key 为 42 的链接。这仍然小于 53 并且 pcurrent.next 仍然不是 null。所以我们再次转到下一个链接。现在，pcurrent.next 是 69。这不小于或等于 53，因此循环终止。

        Link temp = pcurrent.next ;
        pcurrent.next = newLink;
        newLink.next = temp;

现在我们在 69 之后插入。哎呀!我们差一分。所以我们的循环是不正确的。

要解决此问题，我们需要另一个 Link 变量，将其命名为 previous。然后您可以在 previous 之后插入，一切都应该没问题。

    Link pcurrent = pfirst;
    Link previous = null;    // Add this declaration

    Link newLink = new Link(key, value);
    if(pcurrent != null)
    {
        while(pcurrent.key <= newLink.key && pcurrent.next != null)
        {
            previous = pcurrent;     // Update previous
            pcurrent = pcurrent.next;
        }

        // insert newLink between previous and next
        previous.next = newLink;
        newLink.next = current;
    }

您还应该对插入空列表和插入列表开头执行类似的分析。请注意，调试器可以通过准确显示代码正在执行的操作来帮助您进行此分析。只要确保您知道期望会发生什么即可。如果您对调试器显示的内容感到惊讶，那么您就知道存在问题。