Marc Lester Tan

This could be one of the most commonly asked questions in LC. This question has been asked in interviews for the following companies: Amazon, Microsoft, Google, Mathworks, Apple, Oracle, Uber etc.

I have two solutions for this one: Iterative approach and recursive approach.

*** Iterative ***

class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        var previous: ListNode? = null
        var node = head
        while(node?.next != null){
            val temp = node?.next
            node?.next = previous
            previous = node
            node = temp
        }
        
        node?.next = previous
        return node        
    }
}

Runtime: 160 ms, faster than 51.69% of Kotlin online submissions for Reverse Linked List.
Memory Usage: 34 MB, less than 100.00% of Kotlin online submissions for Reverse Linked List.

*** Recursive ***

class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        tailrec fun reverseListRec_(node: ListNode?, previous: ListNode?): ListNode?{
            if(node?.next == null) {
                node?.next = previous
                return node
            }

            val temp = node?.next
            node?.next = previous
            return reverseListRec_(temp, node)
        }
        
        return reverseListRec_(head, null)        
    }
}

Runtime: 156 ms, faster than 65.73% of Kotlin online submissions for Reverse Linked List.
Memory Usage: 34.1 MB, less than 100.00% of Kotlin online submissions for Reverse Linked List.