0

I'm trying to recursively reverse a singly linked list in Java and I learned from this code from Stanford. Could someone please help me translate the C/C++ code to java so that my recursiveReverse() will still be a void method?

Here's the C/C++ solution from Stanford:

void RecursiveReverse(struct node** headRef) {
    struct node* first;
    struct node* rest;

    if (*headRef == NULL) return;

    first = *headRef;
    rest = first->next;

    if (rest == NULL) return;

    RecursiveReverse(&rest);

    first->next->next = first;
    first->next = NULL;
    *headRef = rest;
}

Here's my attempt at the code translation:

public void recursiveReverse(Element<T> currElement) {
    Element<T> first;
    Element<T> rest;

    if (currElement == null) return;

    first = currElement;
    rest = currElement.next;

    if (rest == null) return;

    recursiveReverse(rest);

    first.next.next = first;
    first.next = null;
    head = rest;

}

I originally used "currElement = rest" as the last line but with that, when I started with 1,2,3,null, the output I got was 1, null

But after using head = rest (the linkedlist's original head), I now have 2,1,null.

Could someone please help me translate it correctly so I can get the output as 3,2,1,null? Any help will be much appreciated.

Thanks.

Stralo
  • 474
  • 4
  • 16

2 Answers2

0

Java is passing by value and the C code (not C++) is passing by reference (the pointer to pointer). Hence the two implementations differ. Please have a look at Is Java "pass-by-reference" or "pass-by-value"?

Community
  • 1
  • 1
0

The nicety of C++ is the aliasing, changing a passed variable. Here the same effect can be reached by using a function result.

public Element<T> recursiveReverse(Element<T> currElement) {
    if (currElement == null) return null;

    Element<T> rest = currElement.next;

    if (rest == null) return currElement;

    Element<T> reversed = recursiveReverse(rest);

    rest.next = currElement;
    currElement.next = null;
    return reversed;
}

In java one normally declares at first usage. And I find rest.next more clear than first.next.next.

Joop Eggen
  • 107,315
  • 7
  • 83
  • 138
  • Thanks, Joop, your solution worked perfectly. Is it totally impossible, however, to have the method just change the links of the elements (and thus rearrange them) without returning an element each time it's called? And if so, does it have to do with passing-by-reference (thanks, Dieter!)? I was thinking because we have the elements in memory, we could change their links once we have access to them. – Stralo Feb 20 '14 at 20:32
  • With a reversed list you need to return the last link, and that can only be done _after_ the recursive call, as out-parameter or return value. In java such an out-parameter could be made as array of one element: `void recursiveReverse(Element[] ref)`. – Joop Eggen Feb 20 '14 at 22:22