How to implement Linked List Recursion in KOtlin-CodePudding

I am learning linked list and came across a problem where you are required to reverse a linked list using recursion. Here is the code I wrote:

fun reverseRecurseTraverse1(firstNode: Node<Int>?): Node<Int>? {
    if (firstNode?.next == null) {
        return firstNode
    } else {
        val finalNode = reverseRecurseTraverse1(firstNode.next)
        finalNode?.next = firstNode
        firstNode.next = null
        return finalNode
    }
}

Input:
01234

Output:
40

I get the desired output If I change the line from

finalNode?.next = firstNode

firstNode.next!!.next = firstNode

What am I doing wrong here? When I try to whiteboard finalNode?.next = firstNode makes perfect sense to me and based on my understanding those two lines are essentially doing the same thing. Kindly help me understand this.

CodePudding user response：

It would be useful if you share your "whiteboard logic" and why do you assume finalNode?.next = firstNode is correct and functionally the same as firstNode.next!!.next = firstNode.

Let's get your example: 01234. In the first step firstNode is 0 and after reversing of the remaining sublist, we get 4321. finalNode points at the first element of this reversed sublist, so at 4. Then you add 0 after 4 which is wrong. You should add 0 after 1.

On the other hand, firstNode.next is still pointing at the item that was next to 0 in the original list. It points at 1. By assigning to its next we add 0 where it should be - after 1.

CodePudding user response：

You are almost there, but one line is wrong. What you are doing is:

If your item is null, return it. That seems okay.

If your item is already the last item, return it as first item. Also looks okay.

If your item is not the last item, reverse the rest of the list. Okay.

Take the old last and now first item, and append your old first now last item to it? That doesn't seem right. Don't you want to append your old first and now last item to the last item of the reversed rest?

It would probably help to write a function

fun Node.last(): Node? = if(next == null) this else next!!.last()

that provides the last item of a linked list.

You could use that to append your previously first item to the last item of the reversed rest.

Considering a call reverseRecurseTraverse1(x), can we maybe always tell what reverseRecurseTraverse1(x).last() is without calculating it?