Program for Linked List Reverse in Python

Linked List in Python

A linked list is a data structure that contains a collection of nodes in a sequence. Each node contains data and a pointer to the next node in the sequence. There is a special pointer called the head pointer. This pointer is used to perform operations on the linked list like traversal, insertion, etc. In Python, a linked list is implemented using object-oriented programming. The class Node contains two members, a data field and a reference to the next node. Another class LinkedList is used that stores the reference to the head pointer of the linked list. This class can contain methods to perform CRUD(Create, Read, Update, Delete) operations on the linked list. Below is an implementation of the class Node and the class LinkedList in Python. For simplicity, the data field is taken as an integer. Implementation

Output

Reversing a Linked List in Python

Problem Statement

Given a head pointer of a linked list, the problem is to reverse the linked list in place. This means we are neither allowed to shuffle the data field nor use auxiliary space to create a new linked list. This problem is commonly known as linked list reverse in Python.

Example

Suppose the nodes of the linked list are numbered and links are represented using arrows. So if we are given the $head$ pointer to the linked list: 1 $\rightarrow$ 2 $\rightarrow$ 3 $\rightarrow$ 4 $\rightarrow$ 5 Then our algorithm should provide a linked list reverse in Python as: 5 $\rightarrow$ 4 $\rightarrow$ 3 $\rightarrow$ 2 $\rightarrow$ 1 The new head pointer should be at node 5.

Algorithm

The basic idea of the problem is to traverse the linked list and reverse the links between nodes one at a time. For example, suppose we start with: 1 $\rightarrow$ 2 $\rightarrow$ 3 $\rightarrow$ 4 $\rightarrow$ 5 First, we will reverse the link between node 1 and node 2. 1 $\leftarrow$ 2 Next, we will reverse the link between node 2 and node 3. 1 $\leftarrow$ 2 $\leftarrow$ 3 We will repeat the process until we reverse all the links to get: 1 $\leftarrow$ 2 $\leftarrow$ 3 $\leftarrow$ 4 $\leftarrow$ 5

Reversing a Linked List in Python by an Iterative Approach

Algorithm

Let us consider a simple example to understand the algorithm to get linked list reverse in Python.

Consider two pointers $prev$ pointing to the previous node of the $head$ pointer and $curr$ pointing to the $head$ pointer. Initially, the $prev$ pointer is None.

Step 1: Reverse the link represented by the pointers $prev$ and $curr$. To traverse the rest of the list, we need a temporary variable $next$ that points to the next node in the list after the $curr$ node. Step 2: Update the $prev$ and $curr$ pointer. $prev$ pointer will become $curr$ and $curr$ pointer is updated to $next$ pointer. As we traverse the linked list, we build the linked list reverse in Python.

We perform the above steps until the $curr$ pointer is None.

Implementation

Output

Complexity Analysis

Time Complexity

To solve linked list reverse in Python, we iterate over the list once from start to end and make a constant number of pointer changes. So the time complexity is $O(N)$, where $N$ is the number of nodes present in the linked list.

Time Complexity: $O(N)$

Space Complexity

In the implementation, we are using a constant number of variables, hence the space complexity is $O(1)$.

Space Complexity: $O(1)$

Reversing a Linked List in Python by a Simpler and Tail Recursive Method

Algorithm

In this method, we reverse links in the linked list from the end. The key observation is that, if we remove the first node of the linked list, then we end up with a smaller subproblem. So, we divide the linked list into two parts:

• The first node
• Rest of the linked list

After recursion on the remaining linked list, the link connecting the first node with the linked list is reversed.

Consider the example below. We use a $curr$ pointer for indicating the first node at each recursion.

We call the recursion on the linked list until we are at the last node. In this case, we make this node the new $head$ node and return the $curr$ node.

Now when the function returns, we have a $head$ pointer to the reversed list and the pointer to the $curr$ node. So we add this $curr$ node to the end of the reversed linked list. This is done by reversing the link between $curr$ and $curr.next$.

In this way, we solve the problem linked list reverse in Python recursively.

Implementation

Output

Complexity Analysis

Time Complexity

We iterate over the linked list once using recursion. At each recursion call, we do a constant number of pointer changes, hence the time complexity is $O(N)$, where $N$ is the number of nodes in the linked list.

Time Complexity: $O(N)$

Space Complexity

In the implementation, the number of recursion calls is equal to the number of nodes in the linked list. Each recursive call uses the program stack to store information, hence the space complexity is $O(N)$, where $N$ is the number of nodes in the linked list.

Space Complexity: $O(N)$

Tail Recursive Implementation

Tail Recursion refers to a recursive function in which the function call is the last statement of the function. The function call is the last statement that is executed by the compiler. This is beneficial as compilers can reduce the running time of the program. Since the function call is the last statement to be executed, the compiler does not need to store the states of the current program in the operating system stack. It can just return the result of the function call directly. Multiple stack push and pop operations are not performed in a tail recursive function, so the overall running time and auxiliary space decrease.

The logic to solve linked list reverse in Python using the tail recursive method remains the same, however, a new tail recursive function is added. The function reverseLinkedListTailRecursive reverses the linked list by reversing the links one by one from the beginning until the last node is reached. When the last node is reached, it makes this node the new head of the list.

Complexity Analysis

Time Complexity

We iterate over the linked list once using recursion, hence the time complexity is $O(N)$, where $N$ is the number of nodes in the linked list.

Time Complexity: $O(N)$

Space Complexity

In the implementation, the number of recursion calls is equal to the number of nodes in the linked list. Since we are using tail recursion, there is no need to store the states of the program in the operating system stack, so the space complexity is $O(1)$.

Space Complexity: $O(1)$

Related Programs in Python

• Recursion in Python
• Functions in Python