A recursive solution


  • 210
    G
    class Solution {
    public:
        ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
            if(l1 == NULL) return l2;
            if(l2 == NULL) return l1;
            
            if(l1->val < l2->val) {
                l1->next = mergeTwoLists(l1->next, l2);
                return l1;
            } else {
                l2->next = mergeTwoLists(l2->next, l1);
                return l2;
            }
        }
    };
    

    This solution is not a tail-recursive, the stack will overflow while the list is too long :)
    http://en.wikipedia.org/wiki/Tail_call


  • 0
    L

    This is elegant.


  • 11
    G

    While this is indeed elegant, it should be noted that this would be a terrible solution from a practical point of view, as the stack size would be equal to the length of the merged list, which would result in a stack overflow for relatively small lengths of lists.


  • 4
    P

    Thank you!!
    accordingly, the java version is:

        if(l1 == null) return l2;
        if(l2 == null) return l1;
    
        if(l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l2.next, l1);
            return l2;
        }

  • -3
    S

    No, this code won't get stack overflow. It's space is O(1)! It is not a stack structured recursive method. Instead, it is a queue structured method.


  • 0
    C

    what do you mean by stack structured recursive method and queue structured method? I never heard of the terms. Do you have link or reference to your terms?

    I thought this is an elegant solution, but I am concerned about the stack as well.


  • 12
    S

    Stack structured recursive method means you store median result in a stack for future use. It will take extra space, while queue structured recursive method will take O(1) space. A queue structured method is always written iteratively. Thus it's less used. Most of the recursive method are stack structured. Consider BFS and DFS. No matter how you write them, whether iteratively or recursively. BFS will follow a queue-structured algorithm and DFS will follow a stack-structured algorithm. And this code is actually a stack structured recursive method. Thus it will use extra space, possible risk of stack overflow.


  • 4
    K

    learn a lot from comment!!!


  • 2
    Z

    cool! can't be more simple. get it.


  • 0
    S

    Beautifully written! thank you for the clear and concise answer.


  • 0
    S

    I apologize, but the comments make me a bit confused.

    Will or Will Not this algorithm induce a stack overflow if the List is too long? what's its space complexity?

    • from what I can see, the max stack depth will just be l1.length + l2.length, won't it? each level of stack will possibly store one data element + the recursive function info => space O(n)?

  • 1
    G

    It can definitely induce a stack overflow if the combined length of the two lists are too long. The mergeTwoLists function is called approximately l1.length + l2.length times, so space complexity is O(L+M) where L is the length of the first list, and M is the length of the second. A typical stack size is only around 1MB, so its relatively easy to overflow it.


  • 1
    D

    sadfsadfhjkdsaflsanvl


  • -3
    L
    This post is deleted!

  • 0
    E

    thank you for the answer.!


  • 0
    F

    Nice solution.


  • 0
    P

    How to change it to a non-tail recursive?


  • 4
    V

    The major issue with the problem is it doesn't mention if they are sorted ascending or descending or if both lists are sorted in the same order if you take those into account this is a completely different problem


  • 1
    L

    its cool!veryverycool


  • 1
    V

    @GZShi wouldn't it be better if the line in the else loop is changed to l2->next=mergeTwoLists(l1,l2->next) ? This way the solution becomes more clear,and easier to work out for people trying to solve the same using hand. Thanks !


Log in to reply
 

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