Reverse Linked List


@bluecloud said in Space complexity with stack (example: reverse linked list):
I would like to learn how to calculate space complexity including the stack.
Using this problem as an example: https://leetcode.com/articles/reverselinkedlist/
The recursive Approach #2 solution is said to have a O(n) space complexity. My reasoning is that each "Listnode head" in the parameter takes O(1) space and there will O(n) recursive method calls. During each call the parameter is added to the stack, so a total of n calls * 1 space per parameter = O(n) space. However, the article says "The recursion could go up to n levels deep.". Does "level" just mean how many recursive calls there will be? And I thought this function always (instead of "can") goes to n levels deep.
Also, does the type of recursion (tail vs. nontail) affect the space/time complexity? Approach #2 seems to be tail, and I believe tail recursion is more efficient, but O(n) does not seem particularly spaceefficient.
Thanks!
I think that tne author means that the number of levels are the number of nested call of the recursive function.I think that tail recursion doesn't allocate stack space, but in some language like Java Script for example there is no tail recursion.

Hey,
I just joined leetcode and started with reversing linked list. I got a doubt with recursion code.
public ListNode reverseList(ListNode head) { if (head == null  head.next == null) return head; ListNode p = reverseList(head.next); head.next.next = head; head.next = null; return p; }
As per the recursion model, all function calls will be pushed and later popped. So, the popping starts when head.next will be null and head will be pointing to last node. That's fine....
So, the below function calls where the actual reversing will happen, is returning some pointer 'p'. What will happen then?

@lokesh1729 The recursive function will return a
reversed
linked list and then we can see thathead.next
after reversing will be thetailing
node of the list buthead.next
still points to it so now we have to connecthead
to the tail and finish the recursion.head.next.next = head; head.next = null; //terminate the list, quite critical;

@LHearen hey I understood the program, My actual question is there are two returns, one is returning head. When head.next is null, then it returns head, but while reversing the list, it's returning another pointer 'p'. I got confused. I think that when 'return head;' statement reached, it will be returned and 'return p;' will not be reached. Am I correct? it's like a method with if condition, when the control goes to if condition, that will be returned there.

@lokesh1729 When you're trying to run recursion, you have to
terminate
it somehow and here the firstchecking
statement is the terminating. When program runs after it (if head and head>next is not null), it will automatically revoke itself to reverse its trailing part (head.next now as the parameter)  actually just except for the head, after that we need to connect theoriginal
head back to the reversed end but now the head of the reversed list isp
(because the method is going to return the head pointer to the list, so p here is just pointing to the head of thereversed head.next
).

I have another recursive solution that would still be tail recursive and might be a little easier to understand and verify than the posted solution.
We can pass 2 pointers instead of one to a new internal function:

A pointer to current node after being reversed (i.e. it now points to the previous node).

A pointer to the original next node of the current node before reversing it.
This way we can reverse the current node and at the same time remember what the tail of the list was.ListNode* reverseList(ListNode* head) {
function<ListNode* (ListNode*, ListNode*)> reverse = [&](ListNode *current, ListNode *next) { if (next == NULL) { return current; } else { ListNode *temp = next>next; next>next = current; return reverse(next, temp); } }; return reverse(NULL, head);
}


struct ListNode* reverseList(struct ListNode* head) { struct ListNode newListHead = { 0, NULL }; struct ListNode *p = head;//first node while(p) { struct ListNode *tmpnew = newListHead.next; struct ListNode *tmp = p>next; newListHead.next = p; p>next = tmpnew; p = tmp; } return newListHead.next; }

Would anybody tell me why my solution is wrong?
public class Solution {
public ListNode reverseList(ListNode head) {
if(head == null  head.next ==null) return head;
ListNode pre = null;
ListNode cur = head;
if(cur!= null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}


public ListNode ReverseList(ListNode head) {
if(head == null  head.next == null)
return head;ListNode prev = null, current = head, next = null; while(current.next !=null) { next = current.next; current.next = prev; prev = current; current = next; } current.next = prev; return current; }