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 · Accepted Answer · 2018-08-13 13:43:21Z

1

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.

answered Aug 13, 2018 at 13:43

Jeronimo

2,3972 gold badges15 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Rohan Shenoy Over a year ago

Except the reverse function I'm not allowed to change anything. It's a hackerrank problem, everything else is sealed.

Jeronimo Over a year ago

Ok. But the way it is, you cannot create a linked list with more than one element - it will try to use the tail while it is still None.

Collectives™ on Stack Overflow

reverse a linked list non recursive

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related