java - 将一个节点插入到已排序的整数链表中，以便该列表仍然与下一个的最终成员保持排序

Question

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

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

这是一个面试问题吗？看起来很学术。