algorithm - 黑客排名 : Inserting a Node Into a Sorted Doubly Linked List - Kotlin

Question

只是想知道是否有人能够帮助我解决 Hackerrank 问题 https://www.hackerrank.com/challenges/insert-a-node-into-a-sorted-doubly-linked-list/problem 的 kotlin 实现

我找到了以下解决方案，该解决方案仅通过了 8 项测试中的 3 项。

我对自己做错了什么感到困惑，因为当我在互联网上搜索时，我发现了一个非常相似的 Java 解决方案 - https://www.geeksforgeeks.org/insert-value-sorted-way-sorted-doubly-linked-list/

任何帮助将不胜感激，我对此感到茫然。

fun sortedInsert(llist: DoublyLinkedListNode?, data: Int): DoublyLinkedListNode? {
    val node = DoublyLinkedListNode(data)
    if (llist == null) return node
    
    if (llist.data >= data) {
        node.next = llist
        node.next!!.prev = node
        return node
    }
    
    var current = llist
    while (current?.next != null && current.next!!.data < data) {
        current = current.next
    }
    
    node.next = current?.next
    if (current?.next != null) current.next!!.prev = node
    
    node.prev = current
    current?.next = node
    
    return llist
}

Answer 1

HackerRank 的测试工具对于 Kotlin 来说似乎被破坏了，缺少一个 println 来分隔每个测试用例的输出。一些通过(包括示例测试)的原因是这些的t=1，因此不会触发错误。

查看问题的discussion thread有关此问题的更多投诉。其中一些投诉可以追溯到 3 年前(截至 2021 年 12 月)，这表明即使人力资源部门意识到了这个问题，这也不是解决该问题的首要任务。此外，该问题似乎还会影响 Kotlin 中其他链表问题中的样板，例如 Reverse a Doubly Linked List .

这是翻译成 Java 15 的代码，它通过了 HackerRank 的评审:

public static DoublyLinkedListNode sortedInsert(
    DoublyLinkedListNode llist, int data
) {
    var node = new DoublyLinkedListNode(data);
    if (llist == null) return node;
    
    if (llist.data >= data) {
        node.next = llist;
        node.next.prev = node;
        return node;
    }
    
    var current = llist;
    while (current.next != null && current.next.data < data) {
        current = current.next;
    }
    
    node.next = current.next;
    if (current.next != null) current.next.prev = node;
    
    node.prev = current;
    current.next = node;
    return llist;
}