How to properly reverse Linked List in Kotlin?

user_11888547 0
Viewed 813

I have done both Hackerrank and Leetcode reverse LinkedList questions and my code below works perfectly in Leetcode, passing all test cases but fail some tests cases in hacker rank. The same code written in python or C++ passes all the hacker rank test cases. what might be the problem?

The Kotlin code is

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

It works perfectly in Leetcode and not in Hacker Rank. The following is the Python version which works perfectly in Hacker Rank. The Python code is the same as Kotlin code.

 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

The same code written in C++ also works perfectly in Hacker Rank. What might be the problem?

kotlin data-structures linked-list algorithm python
2 Answers

Here's a solution that seems to work for me:

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)}")
}
user_22946830

This code reverses a single linked list in a recursive way:

data class ReverseInRecursive(
var head: Node? = null)
{
data class Node(var data: Int, var next: Node? = null)

fun reverse(head: Node?): Node? 
{
if (head?.next == null)
return head

val rest = reverse(head.next)
head.next!!.next = head
head.next = null
return rest
}

fun print() 
{
var temp = head
while (temp != null)
{
print("${temp.data} ")
temp = temp.next
}
}

fun push(data: Int)
{
var newNode = Node(data)
if (head == null)
{
head = newNode
return
}

var temp = head
while (temp?.next != null)
{
temp = temp.next
}
temp?.next = newNode

}
}

fun main()
{
var reverseInRecursive = ReverseInRecursive()
reverseInRecursive.push(1)
reverseInRecursive.push(2)
reverseInRecursive.push(3)
reverseInRecursive.push(4)
reverseInRecursive.head = 
reverseInRecursive.reverse(reverseInRecursive.head)
reverseInRecursive.print()
}
user_99719640
Related