Taro Logo

Reverse Linked List

Easy
Meta logo
Meta
2 views
Topics:
Linked Lists

Question

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

  • The number of nodes in the list is the range [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.

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:

  1. Can the linked list be empty? If so, what should I return?
  2. What is the data type of the values stored in the linked list nodes? Are there any constraints on the range of these values?
  3. Should I modify the original linked list in place, or create a new reversed linked list?
  4. Is it possible for the linked list to contain cycles or loops?
  5. Is it acceptable to assume I'm working with a singly linked list as the description implies?

Brute Force Solution

Approach

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:

  1. Start with an empty new list.
  2. Take the first item from the original list.
  3. Put this item at the very beginning of the new list.
  4. Take the next item from the original list.
  5. Put this new item also at the very beginning of the new list, so it is now ahead of the item you already added.
  6. Keep repeating this process, always adding the next item from the original list to the very beginning of the new list.
  7. Once you've moved all the items from the original list, the new list will be the reversed version.

Code Implementation

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

Big(O) Analysis

Time Complexity
O(n)The algorithm iterates through the linked list once, moving each of the n nodes from the original list to the beginning of the new reversed list. Each node is visited and processed exactly once. Therefore, the time complexity is directly proportional to the number of nodes in the linked list, resulting in a linear time complexity of O(n).
Space Complexity
O(N)The provided algorithm creates a new linked list to store the reversed sequence. For each of the N items in the original linked list, a new node is added to the new reversed linked list. Therefore, the auxiliary space required grows linearly with the number of elements in the input linked list, resulting in O(N) space complexity.

Optimal Solution

Approach

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:

  1. Imagine you have a chain of connected links and you want to flip the chain around.
  2. Start by grabbing the first link in the chain.
  3. Change the direction of the first link so it now points to nothing (since it will be the last link).
  4. Take the next link in the chain.
  5. Make it point back to the link you just changed.
  6. Keep doing this for each link: make it point back to the previous one.
  7. As you go, remember to keep track of which link was the previous one and which one is the next one so you don't lose your place.
  8. When you reach the end of the original chain, the new 'first' link will be the original 'last' link, and the chain will be completely reversed.

Code Implementation

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

Big(O) Analysis

Time Complexity
O(n)The algorithm iterates through the linked list once. For each node in the linked list (where n is the number of nodes), it performs a fixed number of operations: changing the next pointer, updating the previous and current nodes. Therefore, the time complexity is directly proportional to the number of nodes in the list. Since the number of operations grows linearly with the input size, the time complexity is O(n).
Space Complexity
O(1)The algorithm iteratively reverses the linked list by changing the 'next' pointers. It uses a few pointer variables to keep track of the current node, the previous node, and the next node during the reversal process. The number of these pointer variables remains constant irrespective of the number of nodes (N) in the linked list. Therefore, the auxiliary space used is constant and does not depend on the input size N.

Edge Cases

CaseHow to Handle
Null head (empty list)Return null immediately as there's nothing to reverse.
Single node listReturn the original head as a single-node list is already reversed.
Two node listStandard 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 valuesThe values of nodes do not affect the reversal process, so duplicates are irrelevant.
List containing only negative valuesNode values are not used for decision making, so negative values are handled the same as positive values.
List containing very large integer valuesThe 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).