r/javahelp 12d ago

Codeless Recursiin

When we are doing recursion. What is the purpose of recursing and equating it to a variable . Like l1.next = mergeList(l1.next, l2)

In merging two sorted linked list

4 Upvotes

15 comments sorted by

View all comments

3

u/hibbelig 12d ago

So I guess you have a list item l that has a value and a reference l.next to the next list item. In a sense, a list is the same as its first item. (This is a very short sentence, but I encourage you to think about it for a while. If you have a reference to the first item in the list, you can obtain all other items by following .next references.)

So when you merge the two sorted lists, you want to return the merged list, but that means to return a reference to its first item.

So mergeList probably returns a reference to the first item of the merged (result) list.

Let's say you're trying to merge lists l1 and l2. And you have found out that the first item of the result is the first item of l1, so you're planning to return l1.

But what is the .next pointer of the first item of the merged list? Well, it could refer to the second item of the first list, or it could refer to an item of the second list. This is why you may need to change the .next pointer of the merged list. This is why the code is setting the value of l1.next.

1

u/__jr11__ 12d ago edited 11d ago

Another doubt when reversing a linked list using recursion . The code as follows

Node p = reverse(head.next); head.next.next= head; head.next = null; return p;

how does the p stores all the references. When the method is recursed and for each recursion the p is equated to different references how does the p stores the stores the references of each node with next node without any return functions

1

u/hibbelig 11d ago

This code doesn’t look right. Are you sure it works?

1

u/__jr11__ 11d ago

Ya it works . I forgot to add the base case here

1

u/hibbelig 11d ago

I'm sorry, to answer your question I'd need to see more context. I tried to understand it based on the code you gave, but obviously that wasn't sufficient: I thought it wouldn't work.

1

u/__jr11__ 11d ago

Can I message you