Python Program to Reverse a linked list
Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing links between nodes.
Examples:
Iterative Method
Python3
|
# Python program to reverse a linked list # Time Complexity : O[n] # Space Complexity : O[n] as 'next' #variable is getting created in each loop. # Node class class Node: # Constructor to initialize the node object def __init__[self, data]: self.data = data self.next = None class LinkedList: # Function to initialize head def __init__[self]: self.head = None # Function to reverse the linked list def reverse[self]: prev = None current = self.head while[current is not None]: next = current.next current.next = prev prev = current current = next self.head = prev # Function to insert a new node at the beginning def push[self, new_data]: new_node = Node[new_data] new_node.next = self.head self.head = new_node # Utility function to print the LinkedList def printList[self]: temp = self.head while[temp]: print [temp.data,end=" "] temp = temp.next # Driver program to test above functions llist = LinkedList[] llist.push[20] llist.push[4] llist.push[15] llist.push[85] print ["Given Linked List"] llist.printList[] llist.reverse[] print ["\nReversed Linked List"] llist.printList[] # This code is contributed by Nikhil Kumar Singh[nickzuck_007] |
Output:
Given Linked List 85 15 4 20 Reversed Linked List 20 4 15 85A Simpler and Tail Recursive Method
Python3
|
# Simple and tail recursive Python program to # reverse a linked list # Node class class Node: # Constructor to initialize the node object def __init__[self, data]: self.data = data self.next = None class LinkedList: # Function to initialize head def __init__[self]: self.head = None def reverseUtil[self, curr, prev]: # If last node mark it head if curr.next is None: self.head = curr # Update next to prev node curr.next = prev return # Save curr.next node for recursive call next = curr.next # And update next curr.next = prev self.reverseUtil[next, curr] # This function mainly calls reverseUtil[] # with previous as None def reverse[self]: if self.head is None: return self.reverseUtil[self.head, None] # Function to insert a new node at the beginning def push[self, new_data]: new_node = Node[new_data] new_node.next = self.head self.head = new_node # Utility function to print the LinkedList def printList[self]: temp = self.head while[temp]: print[temp.data,end=" "] temp = temp.next # Driver program llist = LinkedList[] llist.push[8] llist.push[7] llist.push[6] llist.push[5] llist.push[4] llist.push[3] llist.push[2] llist.push[1] print["Given linked list"] llist.printList[] llist.reverse[] print["\nReverse linked list"] llist.printList[] # This code is contributed by Nikhil Kumar Singh[nickzuck_007] |
Output Given linked list 1 2 3 4 5 6 7 8 Reverse linked list 8 7 6 5 4 3 2 1
Please refer complete article on Reverse a linked list for more details!
Article Tags :
Python Programs
Python DSA-exercises
Python LinkedList-exercises
Read Full Article
Reverse a linked list
Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes.
Examples:
Input: Head of following linked list
1->2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULLInput: Head of following linked list
1->2->3->4->5->NULL
Output: Linked list should be changed to,
5->4->3->2->1->NULLInput: NULL
Output: NULL
Input: 1->NULL
Output: 1->NULL
Reverse LinkedList — Day 6[Python]
Today we will learn how to reverse a linked list. The basic features of the linked list are covered in Day 2 of the 365dayschallenge series. You can follow this link if you require a refresher.
206. Reverse Linked List
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULLOutput: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Can you implement both?
Before we jump into the solution, let us run into a few more examples.
Input: 1->NULLOutput: 1->NULLInput: 1->2->NULL
Output: 2->1->NULLInput: NULL
Output:NULL
Solution — Iterative Approach
To reverse a linked list through iterative approach we would require 3 pointers.
- Holds the previous node.
- Holds the current node.
- Holds the next node.
We just need to learn how to manipulate above three pointers in order to reverse a linked list.
- Initialise previous[A] pointer to “None”.
- Let current pointer[B] point to head of the linked list.
- Run the loop until current reach the end.
- Next pointer[C] points to next of current.
- Next of current pointer points to previous. B -> A
- Previous pointer is now current node.
- Current pointer is now Next of current
def reverseList[self, head: ListNode] -> ListNode:
if head == None or head.next == None:
return head
prev, curr = None, head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
Complexity analysis
Time Complexity
We would be required to traverse through each of the element in LinkedList and that would take O[N] time.
Space Complexity
We are not using any extra data structure to store in the above logic. Hence space complexity is O[1].
Solution — Recursive Approach
When using recursive approach, we need a base condition.
- For this question our base condition is when head is either None or next of head is None. We need to return head when we reach base condition.
- If we have to run through few nodes before reaching the base condition, recursively call the function.
- The next to the next of head is head and next of head is None.
- Then return Current.
def reverseList[self, head: ListNode] -> ListNode:
if head == None or head.next == None:
return head
curr = self.reverseList[head.next]
head.next.next = head
head.next = None
return curr
An animated version of above logic is given below.
Time Complexity
We would be required to traverse through each of the element in LinkedList and that would take O[N] time
Space Complexity
Internally recursive function uses a stack to execute the program. Hence space complexity is O[N].
I would like to improve my writing skills so any suggestions or critiques are highly welcomed.
Reverse a linked list without additional datastructures using python
How to reverse a linked list in python
A typical Linked List
Objective
Given a singly linked list, reverse it without using additional data structures.
Problem Statement
Given a pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes.
Example:
Input: [1,2,3,4,5,NULL]
Output: [5,4,3,2,1,NULL]
Explanation:
Input: [3,4,5]
Output: [5,4,3]
Explanation:
Recursive Approach
The recursive approach to reverse a linked list is simple, just we have to divide the linked lists in two parts and i.e first node and the rest of the linked list, and then call the recursion for the other part by maintaining the connection.
Recursive Approach
Implementation Of Recursive Approach
C++ Implementation
ListNode* reverseList[ListNode* head] { if[!head || ![head->next]] return head; auto res = reverseList[head->next]; head->next->next = head; head->next = NULL; return res; }Java Implementation
static class Node { int data; Node next; Node[int d] { data = d; next = null; } } static Node reverse[Node head] { if [head == null || head.next == null] return head; Node rest = reverse[head.next]; head.next.next = head; head.next = null; return rest; }Python Implementation
def reverse[self, head]: # If head is empty or has reached the list end if head is None or head.next is None: return head # Reverse the rest list rest = self.reverse[head.next] # Put first element at the end head.next.next = head head.next = None # Fix the header pointer return restTime complexity: O[N], Where N is the size of the linked list.
Space complexity: O[1]