{"id":27294,"date":"2018-01-20T20:47:14","date_gmt":"2018-01-20T15:17:14","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27294"},"modified":"2018-01-20T20:47:14","modified_gmt":"2018-01-20T15:17:14","slug":"python-algorithm-write-function-reverse-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-algorithm-write-function-reverse-linked-list\/","title":{"rendered":"Python Algorithm – Write a function to reverse a linked list"},"content":{"rendered":"

Given pointer to the head node of a linked list, the task is to reverse the linked list.<\/p>\n

Examples<\/strong>:<\/p>\n

Input : Head of following linked list  \r\n       1->2->3->4->NULL\r\nOutput : Linked list should be changed to,\r\n       4->3->2->1->NULL\r\n\r\nInput : Head of following linked list  \r\n       1->2->3->4->5->NULL\r\nOutput : Linked list should be changed to,\r\n       5->4->3->2->1->NULL\r\n\r\nInput : NULL\r\nOutput : NULL\r\n\r\nInput  : 1->NULL\r\nOutput : 1->NULL<\/pre>\n
\n[ad type=”banner”]\n
Iterative Method<\/strong>
\nIterate trough the linked list. In loop, change next to prev, prev to current and current to next<\/p>\n
Python Programming:<\/strong><\/p>\n
 
 <\/div> 
# Python program to reverse a linked list # Time Complexity : O(n)# Space Complexity : O(1) # 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 linked LinkedList    def printList(self):        temp = self.head        while(temp):            print temp.data,            temp = temp.next  # Driver program to test above functionsllist = 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)<\/code><\/pre> <\/div>\n
Given linked list\r\n85 15 4 20 \r\nReversed Linked list \r\n20 4 15 85<\/pre>\n
Time Complexity:<\/strong> O(n)
\nSpace Complexity:<\/strong> O(1)<\/p>\n[ad type=”banner”]\n
Recursive Method:<\/strong><\/p>\n
   1) Divide the list in two parts - first node and rest of the linked list.\r\n   2) Call reverse for the rest of the linked list.\r\n   3) Link rest to first.\r\n   4) Fix head pointer<\/pre>\n<\/div>\n
\"Write<\/p>\n
C Programming:<\/strong><\/p>\n
 
 <\/div> 
void recursiveReverse(struct node** head_ref){    struct node* first;    struct node* rest;          \/* empty list *\/    if (*head_ref == NULL)       return;        \/* suppose first = {1, 2, 3}, rest = {2, 3} *\/    first = *head_ref;      rest  = first->next;     \/* List has only one node *\/    if (rest == NULL)       return;        \/* reverse the rest list and put the first element at the end *\/    recursiveReverse(&rest);    first->next->next  = first;           \/* tricky step -- see the diagram *\/    first->next  = NULL;               \/* fix the head pointer *\/    *head_ref = rest;              }<\/code><\/pre> <\/div>\n
Time Complexity:<\/strong> O(n)
\nSpace Complexity:<\/strong> O(1)<\/p>\n[ad type=”banner”]\n
Python Programming:<\/strong><\/p>\n
 
 <\/div> 
# 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 linked LinkedList    def printList(self):        temp = self.head        while(temp):            print temp.data,            temp = temp.next  # Driver programllist = 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)<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
Output:<\/strong><\/p>\n
Given linked list\r\n1 2 3 4 5 6 7 8\r\n\r\nReversed linked list\r\n8 7 6 5 4 3 2 1<\/pre>\n","protected":false},"excerpt":{"rendered":"
Python Algorithm – Write a function to reverse a linked list – Linked List – Given pointer to the head node of a linked list, the task is to reverse<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79476,4148,79478],"tags":[80299,81347,81346,81349,80298,80296,81345,80300,81342,81348,80297,81344,81343],"class_list":["post-27294","post","type-post","status-publish","format-standard","hentry","category-linked-list","category-python","category-singly-linked-list","tag-algorithm-to-reverse-a-linked-list-in-data-structure","tag-how-to-reverse-a-linked-list-c","tag-how-to-reverse-a-linked-list-in-c","tag-how-to-reverse-a-linked-list-python","tag-reverse-a-linked-list-algorithm","tag-reverse-a-linked-list-c","tag-reverse-a-linked-list-in-groups-of-size-k","tag-reverse-a-linked-list-recursively-c","tag-reverse-a-linked-list-using-recursion","tag-reverse-doubly-linked-list-java","tag-reverse-linked-list-recursive-java","tag-reversing-a-linked-list-in-c-with-explanation","tag-reversing-a-linked-list-in-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27294","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27294"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27294\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27294"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27294"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27294"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}