045.md

206. Reverse Linked List

Difficulty: 🟢 Easy

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

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

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?

Solutions

Name of solution

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

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        new_head = None
        while head:
            node = head
            head = head.next
            node.next = new_head
            new_head = node
        return new_head

The given solution approach follows these steps:

1. Initialize a new_head variable to None.
2. Iterate over the linked list using a while loop until the head becomes None.
3. Inside the loop, store the current head node in a temporary variable node.
4. Update the head node to point to the next node in the original list.
5. Update the next pointer of the node to point to the new_head.
6. Update the new_head to be the current node.
7. Repeat steps 3-6 until the end of the linked list is reached.
8. Return the new_head, which will be the head of the reversed linked list.

Complexity Analysis

The time complexity of the algorithm is O(n), where n is the number of nodes in the linked list. The algorithm iterates over the linked list once, reversing the pointers.

The space complexity of the algorithm is O(1) because it uses a constant amount of additional space.

Summary

The given solution reverses a singly linked list by iterating over the list and updating the pointers. It uses a temporary variable to store the current node, updates the next pointer of each node to point to the previous node, and updates the new head to be the current node. The algorithm has a time complexity of O(n) and a space complexity of O(1).

NB: If you want to get community points please suggest solutions in other languages as merge requests.