CODEWITHSUNDEEP
javacollections
ericbae
ericbae

Reputation: 9644

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 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?

Upvotes: 3

Views: 2366

Answers (3)

Saurabh Patil
Saurabh Patil

Reputation: 4462

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!

Upvotes: 0

axtavt
axtavt

Reputation: 242766

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  ]

Upvotes: 5

Bozho
Bozho

Reputation: 597324

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

Upvotes: 4

Related Questions