Problem Description

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

Example 1:

206.1.jpg

  • Input: head = [1,2,3,4,5]
  • Output: [5,4,3,2,1]

Example 2:

206.2.jpg

  • Input: head = [1,2]
  • Output: [2,1]

My Idea

The idea here is to traverse the linked list and for every element reverse the direction of the link.

My solution

from typing import Optional
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Time Complexity: O(n)
def reverseList(head:Optional[ListNode])->Optional[ListNode]:
    prev = None
    curr = head

    while curr:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    return prev