Reputation: 1313
public class LinkedList {
Node head = null;
int nodeCount= 0;
int counter = 0;
LinkedList() {
head = null;
}
public Node reverseTest(Node L) {
if(L == null || L.next ==null) {
return L;
}
Node remainingNode = reverseTest(L.next);
Node cur = remainingNode;
while(cur.next !=null) {
cur=cur.next;
}
L.next = null;
cur.next = L;
return remainingNode;
}
}
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList FriendList = new LinkedList();
FriendList.insertNode("First");
FriendList.insertNode("Second");
FriendList.insertNode("Third");
FriendList.insertNode("Fourth");
FriendList.reverseTest(FriendList.head);
// FriendList.copyObject(FriendList.head);
String NameList = FriendList.toString();
System.out.println(NameList);
System.out.println("Finish");
}
}
Confusion:
In the reverseTest
method which is recursive after returning first L value from this line
if(L == null || L.next ==null) {
return L;
}
we pass the value to remainingNode
in this line
Node remainingNode = reverseTest(L.next);
then we copy it to cur
variable
Node cur = remainingNode;
when we reach the line
cur.next = L;
it updates the cur.next
with L, but it also updates
remainingNode.next = L
I don't understand. How? Can someone point me what should I look into?
Upvotes: 0
Views: 92
Reputation: 109623
Fist the head node will be changed by the reversal, so it is an in-out parameter. In java: in-parameter + result:
friendList.head = FriendList.reverseTest(FriendList.head);
The shown code loops/recurses much. The reason being that the recursion is done on the rest, and then the first element appended at the tail. Quite unnatural, circumstantial.
For a recursive solution, one should go a more natural solution. For such recursive solutions, an extra parameter helps. Here we have a to-do-list and a done-list as parameters.
Now you can delay, use "future" results:
public Node reverseTest(Node L) {
return reverseRecursively(L, null);
}
private Node reverseRecursively(Node node, Node reversed) {
if (node == null) {
return reversed;
}
Node next = node.next;
node.next = reversed;
reversed = node;
return reverseRecursively(next, reversed);
}
Here node
will be the sublist of to-dos, and reversed
the partial result of already reversed nodes.
This is called tail-recursion as there is a single recursive call at the end. So it can easily be written iteratively as a single loop.
Upvotes: 0
Reputation: 20
cur and remaining node are pointing to the same memory address. whatever you do to one will affect the other. You want them to point to two different memory locations.
Upvotes: 1
Reputation: 4047
There is a while
loop in between Node cur = remainingNode;
and cur.next = L
:
while(cur.next !=null){
cur=cur.next;
}
Hence, cur
and remainingNode
are not pointing to the same node. cur
is now pointing to the last node of the list starting from remainingNode
.
Upvotes: 0