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.

comments powered by Disqus