My recursive way to solve this problem(JAVA, easy understanding)


  • 105

    Hello every one, here is my code, simple but works well:

    public class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if(l1 == null){
                return l2;
            }
            if(l2 == null){
                return l1;
            }
            
            ListNode mergeHead;
            if(l1.val < l2.val){
                mergeHead = l1;
                mergeHead.next = mergeTwoLists(l1.next, l2);
            }
            else{
                mergeHead = l2;
                mergeHead.next = mergeTwoLists(l1, l2.next);
            }
            return mergeHead;
        }
    }

  • 3
    C

    Wow! Marvelous! Every time you find the smaller one as the merge head meanwhile it's the last recursive procession's next node. Easy to understand and easy to code.


  • 1

    Thanks!!!!!!!!!!!!!!!!!!


  • 0
    K

    nice solution!

    (potentially stack overflow)


  • 0
    A

    @zwangbo Very nice solution. Thanks for sharing it


  • 2

    It will occur stack overflow if list length is too long.


  • 0
    L

    Thanks, your code is very to understand!


  • 0
    J

    However the recursive solution would modify the input parameters! This is not good, and I've no idea whether it's bad~


  • 0
    M

    cool!thanks!


  • 2
    Y

    Hi, I make a small change for your code.
    It is much more simple.

    public 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(l1, l2.next);
                return l2;
            }
        }
    }
    

  • 0
    K
    This post is deleted!

  • 0
    V

    @zwangbo What is the time complexity of this algorithm ?
    Is it O(n+m) ? length of first list and length of second list


  • 0
    D

    这里用的ListNode是自定义的数据结构,在实际项目编码中用LinkedList或ArrayList怎么实现呢


Log in to reply
 

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