Reversing LinkedList in Java

I am looking at the solution in this post 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 res开发者_如何学Pythont 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?

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  ]

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

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

secondElem.next = list;
return reverseRest;

Let me explain you the 2 lines that you did not understand one by one:

1.secondElem.next = list;

I think the creation of secondElem introduces additional complexity. The variable secondElem is not needed at all.

Instead of this:

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

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

Use this:

ListNode reverseRest = Reverse(list.next);    
list.next.next = list;

It is easier to grasp. The last line of code clearly shows the list reversal process in itself!

2. return reverseRest;

Look at the usage of reverseRest variable & understand it's purpose. It's only purpose is to percolate the value of the original tail of the list to the end of all the recursion calls, so that we can return the original tail (which is also the new head) to the main function that called the Reverse function. You must quickly get this by understanding that we are not at all changing the value of variable reverseRest in between the recursion calls - whatever we receive as return value from Reverse(secondElem) we are returning it "as it is" from the function!