"""Hackerrank Problem: https://www.hackerrank.com/challenges/reverse-a-doubly-linked-list/problem

You’re given the pointer to the head node of a doubly linked list. Reverse the order of the nodes in the list. The head
node might be NULL to indicate that the list is empty. Change the next and prev pointers of all the nodes so that the
direction of the list is reversed. Return a reference to the head node of the reversed list.
"""

import math
import os
import random
import re
import sys


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


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


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

        node = node.next

        if node:
            fptr.write(sep)


# Complete the reverse function below.

#
# For your reference:
#
# DoublyLinkedListNode:
#     int data
#     DoublyLinkedListNode next
#     DoublyLinkedListNode prev
#
def reverse(head):
    """Function to reverse a doubly linked list

    Args:
        head (DoublyLinkedListNode): Head node of a doubly linked list

    Returns:
        (DoublyLinkedListNode): The head of the newly reversed doubly linked list
    """
    new_head = head
    current = head
    while current:
        temp = current.prev
        current.prev = current.next
        current.next = temp
        new_head = current
        current = current.prev
    return new_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()

"""Hackerrank Problem: https://www.hackerrank.com/challenges/reverse-a-doubly-linked-list/problem

You’re given the pointer to the head node of a doubly linked list. Reverse the order of the nodes in the list. The head
node might be NULL to indicate that the list is empty. Change the next and prev pointers of all the nodes so that the
direction of the list is reversed. Return a reference to the head node of the reversed list.
"""

import math
import os
import random
import re
import sys


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


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


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

        node = node.next

        if node:
            fptr.write(sep)


# Complete the reverse function below.

#
# For your reference:
#
# DoublyLinkedListNode:
#     int data
#     DoublyLinkedListNode next
#     DoublyLinkedListNode prev
#
def reverse(head):
    """Function to reverse a doubly linked list

    Args:
        head (DoublyLinkedListNode): Head node of a doubly linked list

    Returns:
        (DoublyLinkedListNode): The head of the newly reversed doubly linked list
    """
    new_head = head
    current = head
    while current:
        temp = current.prev
        current.prev = current.next
        current.next = temp
        new_head = current
        current = current.prev
    return new_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()

Hackerrank Problem: https://www.hackerrank.com/challenges/reverse-a-doubly-linked-list/problem  You’re given the pointer to the head node of a doubly linked list. Reverse the order of the nodes in the list. The head node might be NULL to indicate that the list is empty. Change the next and prev pointers of all the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list. # Complete the reverse function below. # # For your reference: # # DoublyLinkedListNode: #     int data #     DoublyLinkedListNode next #     DoublyLinkedListNode prev # Function to reverse a doubly linked list      Args:         head (DoublyLinkedListNode): Head node of a doubly linked list      Returns:         (DoublyLinkedListNode): The head of the newly reversed doubly linked list