Given the head
of a singly linked list, reverse the list, and return the reversed list.
[0, 5000]
.-5000 <= Node.val <= 5000
For example:
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Can you implement a function to reverse a singly linked list? Consider both iterative and recursive solutions. What are the time and space complexities of your solution? Address potential edge cases such as an empty list or a single-node list. Provide an implementation example in Java.
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force way to reverse a linked list is to create a new list in reverse order. We essentially take each item one by one, and put it in front of the new list we are building.
Here's how the algorithm would work step-by-step:
class ListNode:
def __init__(self, value=0, next_node=None):
self.value = value
self.next_node = next_node
def reverse_linked_list_brute_force(head):
new_head = None
current_node = head
while current_node:
# Store the next node to process
next_node = current_node.next_node
# Put current node at the beginning of new list
current_node.next_node = new_head
# Update new_head to point to the current node.
new_head = current_node
# Move on to the next node
current_node = next_node
return new_head
The best way to reverse a linked list is to essentially walk through it once, changing the direction each element points. Instead of making a new copy, you rearrange the existing elements to achieve the reversal efficiently. It's like turning a train around by uncoupling and re-coupling each car in the opposite direction.
Here's how the algorithm would work step-by-step:
def reverse_linked_list(head):
previous_node = None
current_node = head
# Iterate through the list, changing pointer directions
while(current_node is not None):
# Store the next node before reversing the pointer
next_node = current_node.next
# Reverse the pointer of the current node
current_node.next = previous_node
# Move pointers one position ahead
previous_node = current_node
# Moving current_node helps move forward
current_node = next_node
# 'previous_node' will be the new head
return previous_node
Case | How to Handle |
---|---|
Null head (empty list) | Return null immediately as there's nothing to reverse. |
Single node list | Return the original head as a single-node list is already reversed. |
Two node list | Standard reversal logic correctly handles the swap between the two nodes. |
List with a large number of nodes (memory usage) | Iterative solution is preferred due to O(1) space complexity and avoidance of stack overflow issues with recursion in very large lists. |
List with duplicate values | The values of nodes do not affect the reversal process, so duplicates are irrelevant. |
List containing only negative values | Node values are not used for decision making, so negative values are handled the same as positive values. |
List containing very large integer values | The values stored in the nodes are not directly manipulated, thus integer overflow within the values themselves should not impact the reversal logic. |
Cyclic list (invalid input - should not occur in a singly linked list) | The iterative solution will result in infinite loop, so explicitly add a check to see if any pointer goes back to an already processed node and handle accordingly (e.g. throw error/return null). |