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.
Input Format
You have to complete the Node* Reverse(Node* head) method which takes one argument - the head of the doubly linked list. You should NOT read any input from stdin/console.
Output Format
Change the next and prev pointers of all the nodes so that the direction of the list is reversed. Then return the head node of the reversed list. Do NOT print anything to stdout/console.
Sample Input NULL NULL <-- 2 <--> 4 <--> 6 --> NULL
Sample Output
NULL
NULL <-- 6 <--> 4 <--> 2 --> NULL
Explanation 1. Empty list, so nothing to do. 2. 2,4,6 become 6,4,2 o reversing in the given doubly linked list.
---------------------------------------------------------------------------------------------------------------
/*
Reverse a doubly linked list, input list may also be empty
Node is defined as
struct Node
{
int data;
Node *next;
Node *prev;
}
*/
Node* Reverse(Node* head)
{
Node *cur = head,*temp = new Node; while(cur !=NULL){ temp->next = cur->next; temp->prev = cur->prev; cur->next = temp->prev; cur->prev = temp->next; cur = temp->next; if(cur!=NULL){ head = cur; } } return head;
}
------------------------------------------------------------------------------------------------------------
Given the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That is, change the next and prev pointers of the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list.
Note: The head node might be NULL to indicate that the list is empty.
Function Description
Complete the reverse function in the editor below.
reverse has the following parameter(s):
- DoublyLinkedListNode head: a reference to the head of a DoublyLinkedList
Returns
- DoublyLinkedListNode: a reference to the head of the reversed list
Input Format
The first line contains an integer t, the number of test cases.
Each test case is of the following format:
- The first line contains an integer n, the number of elements in the linked list.
- The next n lines contain an integer each denoting an element of the linked list.
Constraints
- 1 <= t <= 10
- 0 <= n <= 1000
- 0 <= DoublyLinkedListNode.data <= 1000
Output Format
Return a reference to the head of your reversed list. The provided code will print the reverse array as a one line of space-separated integers for each test case. Sample Input
1
4
1
2
3
4
Sample Output
4 3 2 1
Explanation
The initial doubly linked list is: 1 <-> 2 <-> 3 <-> 4 -> NULL
The reversed doubly linked list is: 4 <-> 3 <-> 2 <-> 1 -> NULL Solution
#!/bin/python3
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):
prev = None
d_node = head
while d_node != None:
temp = d_node.next
d_node.next = prev
prev = d_node
d_node = temp
head = 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()
SOMJANG/CODINGTEST_PRACTICE
1일 1문제 since 2020.02.07. Contribute to SOMJANG/CODINGTEST_PRACTICE development by creating an account on GitHub.
github.com
Given a Doubly Linked List, the task is to reverse the given Doubly Linked List. See below diagrams for example. (a) Original Doubly Linked List (b) Reversed Doubly Linked List Here is a simple method for reversing a Doubly Linked List. All we need to do is swap prev and next pointers for all nodes, change prev of the head (or start) and change the head pointer in the end.
Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.
|
void reverse(Node **head_ref)
Node *current = *head_ref;
current->prev = current->next;
void push(Node** head_ref, int new_data)
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref)->prev = new_node ;
void printList(Node *node)
cout << node->data << " ";
cout << "Original Linked list" << endl;
cout << "\nReversed Linked list" << endl;
|
|
void reverse(struct Node **head_ref)
struct Node *temp = NULL;
struct Node *current = *head_ref;
current->prev = current->next;
void push(struct Node** head_ref, int new_data)
(struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref)->prev = new_node ;
void printList(struct Node *node)
printf("%d ", node->data);
struct Node* head = NULL;
printf("\n Original Linked list ");
printf("\n Reversed Linked list ");
|
|
while (current != null) {
current.prev = current.next;
Node new_node = new Node(new_data);
void printList(Node node)
System.out.print(node.data + " ");
public static void main(String[] args)
LinkedList list = new LinkedList();
System.out.println("Original linked list ");
System.out.println("The reversed Linked List is ");
|
|
def __init__(self, data):
while current is not None:
current.prev = current.next
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
def printList(self, node):
print ("\nOriginal Linked List")
print ("\nReversed Linked List")
|
|
public class LinkedList {
while (current != null) {
current.prev = current.next;
Node new_node = new Node(new_data);
void printList(Node node)
Console.Write(node.data + " ");
public static void Main(String[] args)
LinkedList list = new LinkedList();
Console.WriteLine("Original linked list ");
Console.WriteLine("The reversed Linked List is ");
|
|
while (current != null) {
current.prev = current.next;
function push(new_data) {
var new_node = new Node(new_data);
function printList(node) {
document.write(node.data + " ");
document.write("Original linked list <br/>");
document.write("The reversed Linked List is <br/>");
|
Output: Original linked list
10 8 4 2
The reversed Linked List is
2 4 8 10Time Complexity: O(N), where N denotes the number of nodes in the doubly linked list.
Auxiliary Space: O(1)
We can also swap data instead of pointers to reverse the Doubly Linked List. Method used for reversing array can be used to swap data. Swapping data can be costly compared to pointers if the size of the data item(s) is more.
Please write comments if you find any of the above codes/algorithms incorrect, or find better ways to solve the same problem. Method 2: The same question can also be done by using Stacks. Steps:
- Keep pushing the node’s data in the stack. -> O(n)
- The keep popping the elements out and updating the Doubly Linked List
|
Node* new_node = new Node(new_data);
void printList(Node* node)
cout << node->data << " ";
cout << "Original linked list " << endl;
list.printList(list.head);
cout << "The reversed Linked List is " << endl;
list.printList(list.head);
|
|
Stack<Integer> stack = new Stack<>();
Node new_node = new Node(new_data);
void printList(Node node)
System.out.print(node.data + " ");
public static void main(String[] args)
LinkedList list = new LinkedList();
System.out.println("Original linked list ");
System.out.println("The reversed Linked List is ");
|
|
def __init__(self, data):
def reverseUsingStacks(self):
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
def printList(self, node):
print("original doubly-linked list")
print(" reversed doubly-linked list")
|
|
using System.Collections;
using System.Collections.Generic;
Stack stack = new Stack();
temp.data = (int)stack.Pop();
public void Push(int new_data)
Node new_node = new Node(new_data);
public void printList(Node node)
Console.Write(node.data + " ");
public static void Main(string[] args)
LinkedList list = new LinkedList();
Console.WriteLine("Original linked list ");
Console.WriteLine("The reversed Linked List is ");
|
|
this.next = this.prev = null;
let new_node = new Node(new_data);
document.write(node.data + " ");
document.write("Original linked list <br>");
document.write("The reversed Linked List is <br>");
|
Output
Original linked list
10 8 4 2
The reversed Linked List is
2 4 8 10
Time Complexity: O(N)
Auxiliary Space: O(N) In this method, we traverse the linked list once and add elements to the stack, and again traverse the whole for updating all the elements. The whole takes 2n time, which is the time complexity of O(n).
Article Tags : Practice Tags :
| 
