Reverse Linked List | Dataford Interview Questions

Given the head of a singly linked list, reverse the list and return the new head. Implement both an iterative solution and a recursive solution.

Formal Specification

Write a function that accepts the head node of a singly linked list. Each node has two fields: val and next. Return the head node of the reversed list. The list may be empty or contain one node.

You should provide two approaches in your solution: one using iteration and one using recursion.

Constraints

0 <= number of nodes <= 10^5
-10^9 <= Node.val <= 10^9
The input is a singly linked list
The solution should run in linear time

Function Signature

def reverse_list(head):

Your question is Reverse Linked List. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem