Reversing LinkedList in Java

Question

I am looking at the solution in this post http://stackoverflow.com/questions/354875/reversing-a-linked-list-in-java-recursively

I copied the one of the solutions below. I've implemented it and it works fine.

public ListNode Reverse(ListNode list)
{
    if (list == null) return null; // first question

    if (list.next == null) return list; // second question

    // third question - in Lisp this is easy, but we don't have cons
    // so we grab the second element (which will be the last after we reverse it)

    ListNode secondElem = list.next;

    // bug fix - need to unlink list from the rest or you will get a cycle
    list.next = null;

    // then we reverse everything from the second element on
    ListNode reverseRest = Reverse(secondElem);

    // then we join the two lists
    secondElem.Next = list;

    return reverseRest;
}

What I do NOT understand is, however, is the last few lines.

secondElem.next = list;
return reverseRest;

It seems we are not returning the secondElem at all? But I debugged through the code and looks like secondElem is already inside reverseRest. Is this because it's a reference by value in Java and it's automatically updated when secondElem.Next=list is applied?

Answer 1

If your goal is to simply reverse the list, use Collections.reverse(list)

Answer 2

Don't think about passing semantics, think in terms of objects in memory and variables containing references to them.

Initial state:

(list)
   |
   V
[  1  ] -> [  2  ] -> ... -> [  N  ]

After list.next = null;:

(list)   (secondElem)
   |          |
   V          V
[  1  ]    [  2  ] -> ... -> [  N  ]

After recursive call:

(list)   (secondElem)      (reverseRest)
   |          |                 |
   V          V                 V
[  1  ]    [  2  ] <- ... <- [  N  ]

Final state after secondElem.Next = list;:

(list)   (secondElem)      (reverseRest)
   |          |                 |
   V          V                 V
[  1  ] <- [  2  ] <- ... <- [  N  ]