在Java中将数字插入到链表中并保持其排序 [英] Inserting a number into a linked list and keeping it sorted while doing so in java

问题描述

我很自信自己在此代码中是正确的.从逻辑上讲，这对我来说很有意义，但是由于某种原因，程序拒绝运行到特定点.我应该在不使用专有类或哈希表的情况下执行此操作.我的列表节点是一个基本的单链接列表.假设我最初有一个虚拟列表，即0，那么我可以向列表中添加一个数字，仅此而已.除了添加第一个数字之外，这种方法是行不通的.

I feel very confident that i'm right in this code. Logically, it makes sense to me but for some reason the program refuses to run past a certain point. I'm supposed to do this without using proprietary classes or hashtables. My list node is a basic singly linked list. Assuming i have a dummy list at first, 0, i'm able to add one number to the list but that is all. This is the method that will not work beyond adding the first number.

假设我的列表是0-> 2，而我正尝试添加1.

Assuming my list is 0 -> 2. and i'm trying to add 1.

public void insert(int newElement) {
    List marker = head;
    List temp = new List(newElement, null);

    if (head.next == null) {
        head.next = temp;
    } else {
        while (marker.next != null) {
            if (newElement < marker.next.value) {
                temp.next = marker.next;
                marker.next = temp;
                marker = marker.next;
            }
        }
    }
}

推荐答案

public void insert(int val) {
    Item item = new Item(val);

    // the case when there is no item (not counting the dummy head)
    if (head.getNext() == null) {
        head.setNext(item);
        item.setNext(null);
    } else {
        // if there is at least one item....
        Item cursor = head.getNext();
        Item prev = cursor;

        // simply keep looping the list until the new value is less than a value in list
        // if the new value is greater than all the values in the list...
        // then the do-while loop will break when null is reached...
        // at the end of the list
        do {
            if (val < cursor.getVal()) {
                // break and insert
                break;
            }
            prev = cursor;
            cursor = cursor.getNext();
        } while (cursor != null);

        // insert the item
        item.setNext(cursor);

        // the case when the new value is the smallest and is to be inserted at head
        if (val < head.getNext().getVal()) {
            head = item;
        } else prev.setNext(item);
    }
}

这是您的代码段:

if (newElement < marker.next.value) {
    temp.next = marker.next;
    marker.next = temp;
    marker = marker.next;
}

拿一支铅笔和一支纸找出这段代码.您将看到问题所在.进行查看答案，并查看所附图片.这就是您应该如何真正调试有关链表的问题的方法.该图像不是特定于您的代码的，但它应该使您知道如何解决此类问题.

Take a pencil and a paper and trace out this piece of code. You will see what's wrong with it. Take a look at this answer and see the image attached. This is how you should really debug problems regarding linked lists. That image is not specific to your code, but it should give you an idea how to approach this kind of problems.

这篇关于在Java中将数字插入到链表中并保持其排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！