• I would like to learn how to calculate space complexity including the stack.

Using this problem as an example: https://leetcode.com/articles/reverse-linked-list/

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. non-tail) 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 space-efficient.

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) {
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 that `head.next` after reversing will be the `tailing` node of the list but `head.next` still points to it so now we have to connect `head` 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 first `checking` 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 the `original` head back to the reversed end but now the head of the reversed list is `p` (because the method is going to return the head pointer to the list, so p here is just pointing to the head of the `reversed 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.

``````  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);
}
};

``````

}

• ``````struct ListNode* reverseList(struct ListNode* head) {

while (curr)
{
struct ListNode *entry = curr;
curr = curr->next;
}
}
``````

• ``````struct ListNode* reverseList(struct ListNode* head) {
0, NULL
};

struct ListNode *p = head;//first node

while(p)
{
struct ListNode *tmp = p->next;

p->next = tmpnew;

p = tmp;
}

}
``````

• My solution in Python:
time: O(n)
space: O(1)

``````class Solution(object):
"""
:rtype: ListNode
"""

while curt:
nxt = curt.next
curt.next = last
last = curt
curt = nxt
return last
``````

• I use a queue of ListNode*. traverse the whole list and enqueue. Then, while q is not empty, pop from front and instead at head. You could also push all elements in a stack and then add at tail on each pop.

• very good explanation for recursive approach. Thanks !

• About the Approach #2 recursive method, what is the use case of `head == null` in `if (head == null || head.next == null) return head;`. Is it just for the case when reversing a `null` list? Does it have any other meaning?

• Regarding the recursive function, the first time it will actually return is when head.next is NULL. So how can we access head.next.next right after that? Will that not lead to segmentation fault?

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

• @HanYuxin, it should be while (cur != null) instead of if (cur != null)

• Ruby Solution:

``````def reverse_list(head)

previous = nil
nextt = nil

while current != nil
nextt = current.next
current.next = previous
previous = current
current = nextt
end
return previous
end
``````

• This post is deleted!

• Python solution O(n) time, O(1) space:

``````def reverse_list(head):
prev_node = None
next_node = None
while cur_node:
next_node = cur_node.next
cur_node.next = prev_node
prev_node = cur_node
cur_node = next_node
return prev_node
``````

• public ListNode ReverseList(ListNode 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;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.