The Gateway to Computer Science Excellence
0 votes
82 views
What is the time complexity of the best-known algorithm to reverse a doubly linked list?
$A) O(n)$
$B) O(logn)$
$C) O(1)$
$D) O(n^{2})$
in DS by Veteran (54.7k points) | 82 views
+1

like the Singly Linked list as One pass doubly Linked also reverse.

so complexity becomes O(n)

Read complete solution: https://www.geeksforgeeks.org/reverse-doubly-linked-list-set-2/

https://www.hackerrank.com/challenges/reverse-a-doubly-linked-list/forum

0
thanks
0
Just change head pointer to last node of the link list. O(n) time complexity.
0
For doubly linked list we require traversing the head to the last node,so it takes $O(n)$

If there is the circular doubly linked list so it takes $O(1)$ times

please correct me if I'm wrong?
0

I did mistake there. For reversing the doubly linked list we have to swap the next and previous pointer by visiting each and every node and at last change the head to the last node of the linked list.

void swap(node *next, node *temp)
{
 node * temp = NULL;
 temp = next;
 next = prev;
 prev = temp;
}

This code should be run on each and every node of the linked list.

The similar task will be done on the circular linked list.

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,429 answers
195,206 comments
99,913 users