🔗206. Reverse Linked List

Easy | Grind 75 | November 6th Saturday, 2022

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

Example 1

Example 2

Example 3

SOLUTION

We set a variable tail which will be the head of the reversed linked list. Initially, it is set to null because the head of the original linked list should point to null. We will now iterate through the original linked list, and for each node, change the next pointer of the head to point to the tail node. Then change the head to head.next and tail to head. We repeat this until the head points to null and return the tail node which will be the head of the reverse linked list.

# 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]:
        # this is where the first node will point to after reverse
        tail = None
        # there is atleast one node
        if head: 
            # will stop once you traverse all the nodes
            while head != None:     
                temp = head.next
                head.next = tail
                tail = head
                head = temp
        
        return tail

TIME AND SPACE COMPLEXITY

TIME: O(n) where n is the length of the linked list. We have to iterate over all the nodes once.

SPACE: O(1) we only need two variables regardless of the length of the linked list.