Below is a program to reverse a doubly linked list in gfg.

When I try to submit, I get the following error

Your program took more time than expected. Time Limit Exceeded Expected Time Limit 0.00sec.

Can anyone tell me how to decrease my program's time?

Code

public static Node reverseDLL(Node  head)
{
   Node p,cur;
   p=head;
   cur=head.next;

   while(cur!=null)
   {
       if(cur.next==null)
       {
           p.next=cur.next;
           cur.next=head;
           head.prev=cur;
       
           head=cur;
           break;
       }
   
       p.next=cur.next;
       cur.next.prev=p;
   
       cur.next=head;
       head.prev=cur;
   
       head=cur;
       cur=p.next;
   }
   return head;

}

CodePudding user response：

this is classic solution for O(N) time, so I guess time constraint for this task is required to. solve it for O(1). Take a look for this thread: https://www.google.com/url?sa=t&source=web&rct=j&url=https://discuss.codechef.com/t/reverse-a-doubly-linked-list-in-o-1/72850&ved=2ahUKEwjipdrQw_T1AhVYLTQIHahIDx8QFnoECBQQAQ&usg=AOvVaw1c0BDUotM0suEK7I4B9pQs

CodePudding user response：

Your code is not correct:

The prev member of the (original) tail node is not set correctly. It is not set in the if block, but in the previous iteration, where it got its value with cur.next.prev=p, which is setting it to the (original) head node. This creates an infinite loop in the data structure. In the end, none of the prev links is null. It might be that the testing framework keeps following those prev links in circles until a time out happens.

Also, the function assumes that head is not null. This may not be guaranteed.

There are also too many assignments happening. With a doubly linked list it is quite simple: just swap the value of next and prev in every node:

public static Node reverseDLL(Node  head)
{
    if (head == null) {
        return null;
    }
    Node next = head.next;
    while (next != null) {
        head.next = head.prev;
        head.prev = next;
        head = next;
        next = head.next;
    }
    head.next = head.prev;
    head.prev = null;
    return head;
}