reverse double linked list using recursion

Question

I am writing program to reverse double linked list using recursion. I know how to implement iteratively. but stuck in recursion.

Here is what I have

public static Node reverseRecurseDoubleLinkedList(Node node){
        if (node==null || node.next==null)
            return node;
        Node newNode = reverseRecurseDoubleLinkedList(node.next);
        node.next.next=node;
        node.next=null;
        node.prev=newNode;
        return newNode;
    }

I see the prev pointers are not set properly. but next pointers are in fact correct.

Thanks

Possibly same question as stackoverflow.com/questions/354875/… — Duy Anh Pham
– Duy Anh Pham, Commented Apr 11, 2016 at 4:00
@DuyAnhPham: no its not. i am asking for double linked list, read the question first. — brain storm
– brain storm, Commented Apr 11, 2016 at 4:46
There is no point to reverse a double headed link list...You could just swap head and tail references. — Rugal
– Rugal, Commented Apr 11, 2016 at 5:18
@Rugal: Simply swapping head and tail is not sufficient, since the next and prev members of each node would not be properly set. — danbanica
– danbanica, Commented Apr 11, 2016 at 8:33

danbanica · Accepted Answer · 2016-04-14 12:41:52Z

In general, one way to simplify thinking about recursive code is to only consider the guarantees that are offered when a recursive call is complete. You then need to check that these guarantees hold in the basic case that stops recursion (e.g. empty list, or list with a single node), and that they are maintained with each additional recursive call.

There are a few issues in the code provided:

the condition that stopped recursion did not handle correctly the situations when node.next == null. The node.prev field should have been set to null in that case.
the newNode variable name may cause some confusion. It represents the new head of the reversed list (which was the tail of the initial list). I renamed it to newHead.
related to the point above, the assignment node.prev=newNode; is not correct -- we do not want the prev of each node to point to the head of the new list.

After incorporating these aspects, the code below correctly reverses the list:

public static Node reverseRecurseDoubleLinkedList(Node node) {
    if (node == null) {
        return node;
    }

    if (node.next == null) {
        node.prev = null;
        return node;
    }

    Node newHead = reverseRecurseDoubleLinkedList(node.next);
    node.next.next = node;
    node.prev = node.next;
    node.next = null;

    return newHead;
}

Collectives™ on Stack Overflow

reverse double linked list using recursion

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related