Reverse Linked List


  • 1

    Click here to see the full article post


  • 0

    @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/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.


  • 0
    L

    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?


  • 0

    @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;
    
    

  • 0
    L

    @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.


  • 0

    @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).


  • 1
    K

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

    }


  • 0
    M
    struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode *curr = head;
        struct ListNode *newHead = NULL;
        
        while (curr)
        {
            struct ListNode *entry = curr;
            curr = curr->next;
            entry->next = newHead;
            newHead = entry;
        }
        return newHead;
    }
    

  • 0
    J
    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;  
    }  
    

  • 0

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

    class Solution(object):
        def reverseList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if head is None:
                return head
    
            curt, last = head, None
            while curt:
                nxt = curt.next
                curt.next = last
                last = curt
                curt = nxt
            return last
    

  • 0
    D

    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.


  • 0
    L

    very good explanation for recursive approach. Thanks !


  • 0

    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?


  • 0
    M

    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?


  • 0
    H

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


  • 0
    N

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


  • 0

    Ruby Solution:

    def reverse_list(head)
        
        return if head.nil?
        
        current = head
        previous = nil
        nextt = nil
    
        while current != nil
            nextt = current.next
            current.next = previous
            previous = current
            current = nextt
        end
        return previous
    end
    

  • 0
    T
    This post is deleted!

  • 0
    N

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

    def reverse_list(head):
        cur_node = 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
    

  • 0
    R

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

Log in to reply
 

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