1 votes 1 votes 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})$ DS data-structures linked-list + – Lakshman Bhaiya asked Oct 26, 2018 Lakshman Bhaiya 1.3k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Raja Rawal commented Oct 26, 2018 i edited by Raja Rawal Oct 26, 2018 reply Follow Share 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 1 votes 1 votes Lakshman Bhaiya commented Oct 26, 2018 reply Follow Share thanks 0 votes 0 votes Shubhanshu commented Oct 26, 2018 reply Follow Share Just change head pointer to last node of the link list. O(n) time complexity. 0 votes 0 votes Lakshman Bhaiya commented Oct 26, 2018 reply Follow Share 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 votes 0 votes Shubhanshu commented Oct 26, 2018 reply Follow Share 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. 0 votes 0 votes DAWID15 commented Dec 23, 2021 reply Follow Share Yes you’re right. However the pointer can be changed in O(!) but traversing each node, changing their pointers until we reach last node will take o(n) time. So the answer we be O(N). 0 votes 0 votes Please log in or register to add a comment.