Reverse Linked List (Leetcode #206)

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

Answer

This is our first question which involves a linked list.

A linked list is a data structure commonly found in data science consisting of a sequence of elements (Node) each referring to the next element (Node). And unlike arrays linked lists do not require contiguous memory location.

1) Node which is the basic building block of a linked list

2) Linked List which is a collection of Node

In this question, we are given a link list and we are tasked with reversing the order. This is a very common interview question which demonstrates the basic understanding of the linked list.

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        p = None
        c = head
        while c:
            temp = c.next
            c.next = p
            p = c
            c = temp
        return p

We loop through the list with the following steps:

1. Store the Next Node: temp temporarily stores the next node (c.next) to avoid losing it when we change the pointer of the current node.

2. Reverse the Current Node's Pointer: Point the next pointer of the current node (c) to the previous node (p). This reverses the direction of the link for the current node.

3. Move Pointers Forward:

   • Move p to the current node (c). This makes p point to the new head of the partially reversed list.

   • Move c to the next node (temp). This advances c to the next node in the original list.

We repeat these steps until we reach the end of the list (c becomes None).

Time Complexity

Since we loop through the list once, the time complexity is O(N), where N is the number of nodes in the list.

Space Complexity

The space complexity is O(1) since we only use a few pointers and do not require any additional space proportional to the input size.