206-Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/

Problem Statement

Restating Info We’re Already Given:

• Pretty self-evident: reverse the linked list we’re given

Questions/Clarifications to Possibly Ask Interviewer (If starting information we’re given isn’t sufficient to begin):

• Do you care if I do it recursively vs. iteratively?

Discuss Recursive Solution:

We can solve this recursively by calling the function on the next node until either the next node or the next node’s next don’t exist. At that point, we have advanced the pointer as far as we can and return head. Then, we change the head.next.next value to be head (reversing it from pointing from the next value to its prev). We then take the current node’s next pointer and point it to None (comes in handy on the initial first node as we want to its next to point to nothing). At the end, we return the node pointer which pointing at the last node of the un-reversed linked list.

O(n) runtime complexity, O(n) space complexity

Here is a Python Tutor visualization that visually shows what is happening.

Discuss Optimal Solution:

The recursive approach leads to a call stack linear to the number of nodes. We can instead solve this iteratively and reduce the space complexity to O(1). To do so, we need to keep track of the previous node (prev), the current node (head), and the next node(head.next). We first store the head’s next value before reassigning it to prev. We then move prev and head and continue until there isn’t a current node anymore (head is None).

Code Optimal Solution:

https://leetcode.com/submissions/detail/682520213/

Again, here is a Python Tutor visualization.

Runtime/Space Complexity:

The optimal solution has linear runtime still as we have to visit each node once. However, the space is constant as we maintain 3 pointers at any given moment.

Test Cases:

• Empty linked list
• Linked list with no next
• Linked list with many nodes