Jobs

Interviews

Discussions

Reverse Linked List

Easy

Snap

1 view

Topics:

Linked ListsRecursion

Given the head of a singly linked list, reverse the list, and return the reversed list.

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: []

Constraints:

The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Reverse Linked List

Easy

Snap

1 view

Topics:

Linked ListsRecursion

Given the head of a singly linked list, reverse the list, and return the reversed list.

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: []

Constraints:

The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution

Clarifying Questions

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:

Can the linked list be empty, or can the `head` ever be `null`?
Are the values stored in the linked list nodes integers? If so, is there a range I should be aware of?
Should the reversal be done in-place, modifying the original list, or should I create a new reversed list?
Should I return `null` if the input `head` is `null`?
Is a singly linked list guaranteed as the input?

Brute Force Solution

Approach

Imagine a train where each car is linked to the next. The brute force way to reverse this train involves physically rearranging all the cars. We'll meticulously copy the train's data to create a reversed version.

Here's how the algorithm would work step-by-step:

First, walk through the entire train, making a note of the information in each car, one by one.
Next, build a brand new, empty train.
Now, starting from the last piece of information you noted down, create a new train car with that information and add it to the beginning of the new train.
Continue this process, taking each piece of information in reverse order and adding new cars to the beginning of the new train.
Once all the information has been transferred, the new train is the reversed version of the original.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_linked_list_brute_force(head):
    node_values = []

    current_node = head
    while current_node:
        node_values.append(current_node.val)
        current_node = current_node.next

    reversed_head = None

    # Iterate backwards to create the reversed list
    for value in reversed(node_values):

        # Create a new node with the reversed value.
        new_node = ListNode(value)

        # Update head to create the new list.
        new_node.next = reversed_head
        reversed_head = new_node

    return reversed_head

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm first iterates through the linked list of n nodes to store their values in a separate data structure (e.g., an array). This takes O(n) time. Then, it iterates through the stored values in reverse order, creating new nodes and adding them to a new linked list. This second iteration also takes O(n) time. Therefore, the overall time complexity is O(n) + O(n) which simplifies to O(n).

Space Complexity

O(N) – The algorithm first traverses the linked list of size N, storing the value of each node. This implies creating an auxiliary data structure, which is used to store N node values. Next, a new linked list is constructed from these stored values, also requiring space proportional to N. Therefore, the space complexity is O(N).

Optimal Solution

Approach

To reverse a linked list, you essentially want to change the direction each element points. Instead of creating a new list, the optimal solution rearranges the existing one in place, one step at a time. This avoids extra storage and is faster.

Here's how the algorithm would work step-by-step:

Imagine you have a train of linked cars where each car knows which car comes next.
Start with the first car. Change its direction so it points to nothing, like a new last car.
Now, pick up the next car in the original direction. Change its direction to point to the car that was previously first.
Move the first car label to the car you just changed. It is now the beginning of the reversed sequence.
Repeat the process for each car in the original list, always changing the direction and moving the 'first car' label.
Once you reach the end, your original last car is now the first, and all the cars are pointing in the opposite direction.

Code Implementation

def reverse_linked_list(head):
    previous_node = None
    current_node = head

    # We iterate until current_node becomes None
    while(current_node is not None):

        # Store the next node before reversing
        next_node = current_node.next

        # Reverse the current node's pointer
        # This is the core reversal step
        current_node.next = previous_node

        # Move pointers one position ahead
        previous_node = current_node
        current_node = next_node

    # previous_node is now the head of reversed list
    return previous_node

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each node of the linked list exactly once to reverse the pointers. The input size, n, represents the number of nodes in the linked list. For each node, a constant number of operations (pointer manipulation) is performed. Therefore, the total number of operations is directly proportional to the number of nodes, approximating n, which simplifies to O(n).

Space Complexity

O(1) – The algorithm reverses the linked list in-place, meaning it modifies the existing list without creating new data structures that scale with the input size. It uses a few variables to keep track of the current node, the previous node, and the next node while changing the pointers. These variables consume a fixed amount of memory regardless of the number of nodes (N) in the linked list, hence the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty list	Return null immediately; there's nothing to reverse.
List with only one node	Return the original head as it's already reversed.
List with two nodes	Standard iterative or recursive reversal should handle this correctly by swapping the head and head.next, updating pointers.
Long linked list	The iterative approach scales linearly and won't cause stack overflow problems, as opposed to recursion.
List containing duplicate values	The values do not affect the reversal logic, so duplicates are irrelevant; reversal will still work as expected.
List containing negative values	Negative values within the linked list should have no impact on the pointer manipulation during reversal.
Memory limitations for extremely large lists	The iterative approach uses constant extra space, mitigating memory issues related to list size, unlike a naive recursive implementation which could cause stack overflow.
List with loop (corrupted data)	The standard reversal algorithm might lead to an infinite loop; a check for loop using Floyd's cycle detection algorithm could be incorporated before reversing or the reversal algorithm may need to be modified to handle this scenario

Solution

Clarifying Questions

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:

Can the linked list be empty, or can the `head` ever be `null`?
Are the values stored in the linked list nodes integers? If so, is there a range I should be aware of?
Should the reversal be done in-place, modifying the original list, or should I create a new reversed list?
Should I return `null` if the input `head` is `null`?
Is a singly linked list guaranteed as the input?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, walk through the entire train, making a note of the information in each car, one by one.
Next, build a brand new, empty train.
Now, starting from the last piece of information you noted down, create a new train car with that information and add it to the beginning of the new train.
Continue this process, taking each piece of information in reverse order and adding new cars to the beginning of the new train.
Once all the information has been transferred, the new train is the reversed version of the original.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_linked_list_brute_force(head):
    node_values = []

    current_node = head
    while current_node:
        node_values.append(current_node.val)
        current_node = current_node.next

    reversed_head = None

    # Iterate backwards to create the reversed list
    for value in reversed(node_values):

        # Create a new node with the reversed value.
        new_node = ListNode(value)

        # Update head to create the new list.
        new_node.next = reversed_head
        reversed_head = new_node

    return reversed_head

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have a train of linked cars where each car knows which car comes next.
Start with the first car. Change its direction so it points to nothing, like a new last car.
Now, pick up the next car in the original direction. Change its direction to point to the car that was previously first.
Move the first car label to the car you just changed. It is now the beginning of the reversed sequence.
Repeat the process for each car in the original list, always changing the direction and moving the 'first car' label.
Once you reach the end, your original last car is now the first, and all the cars are pointing in the opposite direction.

Code Implementation

def reverse_linked_list(head):
    previous_node = None
    current_node = head

    # We iterate until current_node becomes None
    while(current_node is not None):

        # Store the next node before reversing
        next_node = current_node.next

        # Reverse the current node's pointer
        # This is the core reversal step
        current_node.next = previous_node

        # Move pointers one position ahead
        previous_node = current_node
        current_node = next_node

    # previous_node is now the head of reversed list
    return previous_node

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty list	Return null immediately; there's nothing to reverse.
List with only one node	Return the original head as it's already reversed.
List with two nodes	Standard iterative or recursive reversal should handle this correctly by swapping the head and head.next, updating pointers.
Long linked list	The iterative approach scales linearly and won't cause stack overflow problems, as opposed to recursion.
List containing duplicate values	The values do not affect the reversal logic, so duplicates are irrelevant; reversal will still work as expected.
List containing negative values	Negative values within the linked list should have no impact on the pointer manipulation during reversal.
Memory limitations for extremely large lists	The iterative approach uses constant extra space, mitigating memory issues related to list size, unlike a naive recursive implementation which could cause stack overflow.
List with loop (corrupted data)	The standard reversal algorithm might lead to an infinite loop; a check for loop using Floyd's cycle detection algorithm could be incorporated before reversing or the reversal algorithm may need to be modified to handle this scenario