Reverse a doubly linked list : Hackerrank Solution.

Question

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.

Function Description

Complete the reverse function in the editor below. It should return a reference to the head of your reversed list.

reverse has the following parameter(s):

• head: a reference to the head of a DoublyLinkedList

Input Format

The first line contains an integer , the number of test cases.

Each test case is of the following format:

• The first line contains an integer , the number of elements in the linked list.
• The next  lines contain an integer each denoting an element of the linked list.

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 list was : 1 -> 2 -> 3-> 4-> NULL

The Final list is : 4-> 3-> 2-> 1-> NULL

Solution:

Reversing a doubly linked list is very similar to reversing a singly linked list but the catch here is to take care of the prev pointer.

Steps:

• Create three reference variables ( prevNode , nextNode, currrent ) which are initialised by null.
• Assign head to current, check for edge case i.e if head == null then return null.
• Now we will iterate through the entire list list until we reach the end for doing this we write the condition while(current != null).
• Now we will set the reference in each iteration as prev --> currr --> next;
• In each iteration we will first initialise the nextNode as current.next  now pointer looks like curr--> next;
• Then we assign the current.next as prevNode. prev <-- curr
• We will now take care of the remaining current.prev pointer and assign it with the value nextNode.
• Then we move ahead by moving prevNode to current and current to nextNode, in that order.
• After we finish the iteration we simply return prevNode.  

The code is shared below.

The Time Complexity of the given code is O(n) as we scan the list only once.

static DoublyLinkedListNode reverse(DoublyLinkedListNode head) {

        DoublyLinkedListNode current = null;
        DoublyLinkedListNode prevNode = null;
        DoublyLinkedListNode nextNode = null;
        current = head;
        if(current == null ) return null;
        while(current != null)
        {   nextNode = current.next;
            current.next = prevNode;
            current.prev = nextNode;
            prevNode = current;
            current = nextNode;
        }
        head = prevNode;
    return head;

    }

Thanks for reading, hope it helps.