java - 将一个节点插入到一个排序的整数链表中，这样该列表仍然与最终成员一起排序以供下一个

Question

在 Java 中，如果所有节点都有一个用于 next 的最终成员变量，那么您将如何编写一个方法将节点插入到整数的排序链表中，以使列表仍然保持排序状态，因此您无法更改它们？

标签： javalinked-list

Answer 1

当下一个链接最终确定时：

唯一的理论方法是在列表前面添加一个新节点并移动数据：

void insertSorted(MyList list, int data) {
    list.head = new Node(0, list.head); // Insert in front;
    Node prior = list.head;
    // Invariant condition: prior points to a node (not null) and soon data >= prior.data
    Node current = prior.next;
    while (current != null) {
        if (data < current.data) {
            break;
        }
        prior.data = current.data; // Shift smaller
        prior = current;
        current = current.next;
    }
    prior.data = data;
}

insert:      d
list.head:   a ; b ; c ; e ; f ; g
--------------------------------------
list.head:   X ; a ; b ; c ; e ; f ; g
             a <-´   |   |
                 b <-´   |
                     c <-´
                         d

是面试题吗？看起来很学术。