python - 如何在 Kotlin 中正确反转链表？

Question

我已经完成了 Hackerrank 和 Leetcode 反向 LinkedList 问题，我下面的代码在 Leetcode 中完美运行，通过了所有测试用例，但在 hacker rank 中未通过一些测试用例。用 python 或 C++ 编写的相同代码通过了所有黑客等级测试用例。可能是什么问题？

Kotlin 代码是

if (head == null) return head

var new_head = head
var next_node = new_head.next

while (next_node != null) {
    val temp = next_node.next
    next_node.next = new_head
    new_head = next_node
    next_node = temp
}

head.next = null
return new_head

它在 Leetcode 中完美运行，但在 Hacker Rank 中运行不佳。以下是在 Hacker Rank 中完美运行的 Python 版本。 Python 代码与 Kotlin 代码相同。

 if head is None:
        return None
    else:
        new_head = head
        next_node = new_head.next
        while next_node != None:
            temp_node = next_node.next
            next_node.next = new_head
            new_head = next_node
            next_node = temp_node

        head.next = None
        return new_head

用 C++ 编写的相同代码在 Hacker Rank 中也能完美运行。可能是什么问题？

Answer 1

这是一个似乎对我有用的解决方案:

data class Node(val value: Int, var nextNode: Node?) {
    override fun toString(): String {
        return "Node(value = $value, nextNode = $nextNode)"
    }
}

fun reverseLinkedListIterative(node: Node?): Node? {
    // First establish some pointers we'll be using to store state

    // We're going to be using prev to point to the previous value
    // of the linked list while we iterate through it, because we
    // can't look backwards, unlike a doubly linked list
    var prev: Node? = null

    // curr will represent the node we are currently looking at as
    // we iterate through the linked list
    var curr: Node? = node

    // This pointer will reference the next value in the linked
    // list so that we don't lose it during pointer manipulation
    var next: Node?

    // We're going to iterate through the whole list with curr as
    // our "index". It points to the current node we're manipulating.
    // With each iteration, we make curr equal the next node in the
    // linked list. This loop should terminate once we reach the end
    // of the input list
    while (curr != null) {
        // First save the reference to next node because we're
        // about to reset it
        next = curr.nextNode

        // Then we do the swap. The current node's next node should
        // point to the node that came before it
        curr.nextNode = prev

        // Now we need to advance the prev & curr pointers 1 node
        // forward so that we can keep appending the next node onto
        // prev, building up the reversed linked list
        prev = curr
        curr = next
    }

    // Now that curr is null we have iterated through every value of
    // the linked list and prev now points to the head of the reversed
    // linked list, so we return it
    return prev
}

fun main() {
    val singletonList = Node(value = 0, nextNode = null)
    val twoList = Node(0, nextNode = Node(value = 1, nextNode = null))
    val threeList = Node(0, nextNode = Node(value = 1, nextNode = Node(value = 2, nextNode = null)))
    val fourList = Node(0, nextNode = Node(value = 1, nextNode = Node(value = 2, nextNode = Node(value = 3, nextNode = null))))

    println("reversed null = ${reverseLinkedListIterative(null)}")
    println("reversed singletonList = $singletonList")
    println("reversed twoList = ${reverseLinkedListIterative(twoList)}")
    println("reversed threeList = ${reverseLinkedListIterative(threeList)}")
    println("reversed fourList = ${revIterative(fourList)}")
}