reverse a linked list non recursive

Question

Please check the reverse function below. The rest of the code should be fine. The function is not reversing the doubly linked list for some reason.

#!/bin/python3
import math
import os
import random
import re
import sys

Doubly linked list Node structure

class DoublyLinkedListNode:
    def __init__(self, node_data):
        self.data = node_data
        self.next = None
        self.prev = None

Doubly linked list structure

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def insert_node(self, node_data):
        node = DoublyLinkedListNode(node_data)

        if not self.head:
            self.head = node
        else:
            self.tail.next = node
            node.prev = self.tail
            self.tail = node

Prints the doubly linked list from head to the tail in order.

def print_doubly_linked_list(node, sep, fptr):
    while node:
        fptr.write(str(node.data))

        node = node.next

        if node:
            fptr.write(sep)

Please check the below reverse function as this function does not return the reversed doubly linked list. Check for any errors and let me know.

def reverse(head):
    if head == None:
        return head
    temp = None    
    curr = head
    while(curr is not None):
        temp = curr.prev
        curr.prev = curr.next
        curr.next= temp
        curr = curr.next
    if temp is not None:
        head = temp.prev
    return head




if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())

    for t_itr in range(t):
        llist_count = int(input())

        llist = DoublyLinkedList()

        for _ in range(llist_count):
            llist_item = int(input())
            llist.insert_node(llist_item)

        llist1 = reverse(llist.head)

        print_doubly_linked_list(llist1, ' ', fptr)
        fptr.write('\n')

    fptr.close()

Jeronimo Jeronimo · Accepted Answer · 2018-08-13T13:43:21

You start reversing your list from the head, which has no prev item and therefore breaks out of your while loop. Instead, reversing from the tail should do:

llist1 = reverse(llist.tail)

In general, I think your function reverse should take the whole list (not the head or tail) as an argument, and then build a completely new DoublyLinkedList from the items in it. That would also solve the confusion with your variable names, where llist is a DoublyLinkedList while llist1 is a DoublyLinkedListNode.

edit: I forgot, in insert_node, you should also make self.tail = node if there hasn't been a head yet / first node.

reverse a linked list non recursive

1 Answers