Reverse Linked List

The problem description can be found in LeetCode.

Approach

It is enough to keep track of two consecutive pointers.

At each iteration, we reverse direction of each node's next pointer. In particular, p is used for keeping track of the new head, whereas q traverse the list.

Solution

from typing import Optional


class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p, q = None, head

        while q:
            q_next = q.next
            q.next = p

            p = q
            q = q_next

        return p

Complexity

• Time: $O(n)$
• Space: $O(1)$

Where $n$ is the size of the linked list.