CODEWITHSUNDEEP
javarecursiondata-structureslinked-list
Prince Vijay Pratap
Prince Vijay Pratap

Reputation: 768

Merge two sorted linklist recursively?

I cant find anything wrong with the code but when i submit it two of the testcases giving runtime error . Please help me to figure out that error. I have checked it for atleast 30 custom testcases but it gives right output for all of them.

Code

public static Node mergeTwoList(Node head1, Node head2) {
    Node c = null;        
    if (head1 == null) {
        return head2;
    } else if (head2 == null) {
        return head1;
    }

    if (head1.data < head2.data) {
        c = head1;
        c.next = mergeTwoList(head1.next, head2);
    } else {
        c = head2;
        c.next = mergeTwoList(head1, head2.next); 
    }
    return c;
}

If somebody figure out anything please do tell me.

Upvotes: 1

Views: 744

Answers (1)

codecrazer
codecrazer

Reputation: 535

I think the reason is stackoverflow, because you use recursion, and recursion will produce stack, and if the linklist is long, it may cause stackoverflow.

There is a similar question on leecode, and I solve it with iterative, I paste the solution in my blog, although the explanation is in Madarin, the code can still be your reference. The link is provided below: http://codecrazer.blogspot.tw/2017/07/leetcode-21-merge-two-sorted-lists.html

Upvotes: 1

Related Questions