206. Reverse Linked List#

Difficulty: Easy

Link to Problem: To see the Reverse Linked List problem on LeetCode, click here!

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

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?

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Function to reverse a linked list iteratively
def reverseListIterative(head):
    prev = None
    current = head
    
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    
    return prev

# Function to reverse a linked list recursively
def reverseListRecursive(head):
    if not head or not head.next:
        return head

    new_head = reverseListRecursive(head.next)
    head.next.next = head
    head.next = None

    return new_head

Explanation:#

  1. reverseListIterative(head): This function reverses a linked list iteratively using a loop. Here’s a step-by-step explanation:

    • It takes the head of the input linked list as a parameter.

    • It initializes two pointers, prev and current, initially set to None and the head of the list, respectively.

    • It enters a while loop that continues until current reaches the end of the list (i.e., becomes None).

    • Inside the loop:

      • It stores the next_node which is the next node after current.

      • It updates the next pointer of current to point to the prev node. This effectively reverses the link direction.

      • It moves prev to current and current to next_node, advancing the pointers one step further in the list.

    • Once the loop completes, prev will be pointing to the new head of the reversed list (which was the last node of the original list), so it returns prev.

  2. reverseListRecursive(head): This function reverses a linked list recursively. Here’s how it works:

    • It takes the head of the input linked list as a parameter.

    • The base case is checked: if head is None or head.next is None, meaning the list is empty or has only one node, it returns head as there’s no need to reverse a list with zero or one element.

    • In the recursive case:

      • It calls itself with head.next, effectively moving down the list until it reaches the end.

      • Once it reaches the end, it starts reversing the links:

        • head.next.next is set to head, reversing the link between head and the next node.

        • head.next is set to None to avoid cycles.

    • Finally, it returns the new head of the reversed list, which will be the last node of the original list.

In summary, reverseListIterative reverses the linked list by iterating through it and changing the next pointers, while reverseListRecursive reverses the linked list by recursively reaching the end and then reversing the links on the way back up the recursion stack. Both functions achieve the same result: reversing the linked list.

# Helper function to create a linked list from a list of values
def createLinkedList(values):
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

# Helper function to convert a linked list to a list for testing
def linkedListToList(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result

Let’s explain the two helper functions used in the provided code:

  1. createLinkedList(values):

    • Purpose: This function is used to create a linked list from a list of values. It takes a list of values as input and returns the head of the linked list.

    • How it works:

      • It first checks if the input list values is empty. If it’s empty, it returns None to indicate an empty linked list.

      • If values is not empty, it initializes a head node with the value of the first element in values.

      • It then iterates through the remaining values in values, creating new nodes for each value and linking them together to form a linked list.

      • Finally, it returns the head node of the newly created linked list.

  2. linkedListToList(head):

    • Purpose: This function is used to convert a linked list back into a Python list for testing and output purposes.

    • How it works:

      • It takes the head of the linked list as input.

      • It initializes an empty list called result.

      • It then iterates through the linked list, starting from head, and appends each node’s val (value) to the result list.

      • This process continues until the end of the linked list is reached.

      • Finally, it returns the result list, which contains the values from the linked list in the same order.

These helper functions are used to simplify the process of creating linked lists from lists of values and converting linked lists back into lists, making it easier to work with linked lists in the provided examples and test cases.

Test cases#

# Example 1: Iterative
head1 = [1,2,3,4,5]
head1 = createLinkedList(head1)
reversed_head1 = reverseListIterative(head1)
print(linkedListToList(reversed_head1))

[5, 4, 3, 2, 1]

# Example 2: Recursive
head2 = [1,2]
head2 = createLinkedList(head2)
reversed_head2 = reverseListRecursive(head2)
print(linkedListToList(reversed_head2))

[2, 1]

# Example 3: Empty list
head3 = []
head3 = createLinkedList(head3)
reversed_head3 = reverseListIterative(head3)
print(linkedListToList(reversed_head3))

[]

Let’s analyze the time and space complexity of the two functions:

  1. reverseListIterative(head):

    • Time Complexity: \(O(n)\)

      • The iterative function visits each node in the linked list exactly once in a single pass, where “\(n\)” is the number of nodes in the list. Therefore, the time complexity is linear in the number of nodes.

    • Space Complexity: \(O(1)\)

      • This function uses a constant amount of extra space for the prev, current, and next_node pointers. Regardless of the size of the input list, the amount of additional memory used remains the same, so the space complexity is constant.

  2. reverseListRecursive(head):

    • Time Complexity: \(O(n)\)

      • The recursive function also visits each node in the linked list exactly once. It recursively traverses the list from the head to the tail, reversing the links on the way back. Therefore, like the iterative approach, the time complexity is \(O(n)\), where “\(n\)” is the number of nodes.

    • Space Complexity: \(O(n)\)

      • The recursive function uses space on the call stack for each recursive call. In the worst case, when the list has “\(n\)” nodes, it will create “\(n\)” recursive function calls on the stack, resulting in a space complexity of \(O(n)\). This is because each function call stores information about its state, including the head pointer, until it reaches the base case and starts returning.

In summary:

  • The time complexity of both functions is \(O(n)\) because they both visit each node once.

  • The space complexity of reverseListIterative is \(O(1)\) because it uses a constant amount of extra space.

  • The space complexity of reverseListRecursive is \(O(n)\) due to the recursive function calls and the associated call stack space.

Both functions are efficient in terms of time complexity, but reverseListIterative is more memory-efficient because it uses a constant amount of additional space, while reverseListRecursive uses space on the call stack proportional to the number of nodes in the list.

Challenging Exercises:#

  1. K-Group Reverse: Modify the reverseListIterative function to reverse the linked list in groups of \(K\) elements. For example, if the input linked list is [1, 2, 3, 4, 5, 6], and \(K\) is 3, the output should be [3, 2, 1, 6, 5, 4].

  2. Rotate Linked List: Write a function to rotate a linked list to the right by \(K\) places. For example, if the input is [1, 2, 3, 4, 5] and \(K\) is 2, the output should be [4, 5, 1, 2, 3].