We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Merge two sorted linked lists
  2. Discussions

Merge two sorted linked lists

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 62 Discussions, By:

votes

Please Login in order to post a comment

  • yunussimsiki0
    7 months ago+ 1 comment

    java recursive solution

        static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
            if(head1 == null){
                return head2;
            }
            if(head2 == null){
                return head1;
            }
            
            if(head1.data < head2.data){
                SinglyLinkedListNode nextSortedHead = mergeLists(head1.next, head2);
                head1.next = nextSortedHead;
                return head1;
            }else{
                SinglyLinkedListNode nextSortedHead = mergeLists(head1, head2.next);
                head2.next = nextSortedHead;
                return head2;
            }
        }
    
    9|
    Permalink
  • cagils
    3 months ago+ 2 comments

    js recursive

    function mergeLists(head1, head2) {
        if (!head1) return head2
        if (!head2) return head1
        
        if(head1.data < head2.data){
            return {"data": head1.data, "next": mergeLists(head1.next, head2)}
        }else{
            return {"data": head2.data, "next": mergeLists(head1, head2.next)} 
        }
    }
    
    5|
    Permalink
  • heceoz
    8 months ago+ 4 comments

    python solution:

    def mergeLists(head1, head2):
        if not head1 and not head2:
            return head1
        if not head1:
            return head2
        if not head2:
            return head1
        res = SinglyLinkedListNode(None)
        c = res
        c1 = head1
        c2 = head2
        while c1 and c2:
            print(res)
            if c1.data <= c2.data:
                c.next = c1
                c1 = c1.next
            else:
                c.next = c2
                c2 = c2.next
            c = c.next
        if c1:
            c.next = c1
        if c2:
            c.next = c2
        return res.next
    
    3|
    Permalink
    View more Comments..
  • matt_j_lassen
    7 months ago+ 0 comments

    simple c# code with comments to help you parse it;

    {
    
            //this seems simple, if the lists are sorted, all you need to do is compare each head and insert
            //the smallest one into the new list;
            //the trickiest part of this would be proper node pointer management
            //we need a link to the head of the sorted list and a iterator pointer
            //to make sure we don't lose our place.
            SinglyLinkedListNode sorted = new SinglyLinkedListNode(0);
            SinglyLinkedListNode ind= new SinglyLinkedListNode(0);
            
            //point the sorted list to the first element in the list
            if(head1.data <= head2.data){
                sorted =  head1; //point start of list at it
                ind =  head1; //point iterator at it
                head1 = head1.next; //move head1 pointer over 1
            }
            else{
                sorted = head2; // point start of list at it
                ind = head2; // point iterator at it 
                head2 = head2.next;//move head2 pointer over 1
            }
            
            while( head1 != null || head2!= null)
            {
                if(head1 == null && head2 != null){
                    //continue down head2
                    ind.next = head2;
                    ind = ind.next;
                    head2 = head2.next; //make sure to move head2 over 
                }
                else if(head1 !=null && head2 == null){
                    //head2 is null and we can continue down head1
                    ind.next = head1;
                    ind = ind.next;
                    head1= head1.next; // make sure to move head1 over
                }
                else if(head1.data <= head2.data && ind.next == head1){
                    //head1 is the next lowest number and i next is pointing to it
                    //so we just need to move head1 over 1 as well as i over on same list;
                    head1 = head1.next;
                    ind = ind.next; 
                }
                else if(head1.data <= head2.data && ind.next==head2){
                    //head1 is the next lowest number and i next is not pointing to it
                    //we need to make i next point to head1 then move head1 and iterator over
                    ind.next = head1;
                    head1 =head1.next;
                    ind = ind.next;
                }
                else if(head1.data > head2.data && ind.next== head1){
                    //head2 is the next lowest data and i next is not pointing to it
                    //make i next point to head2 and move head2 and iterator over
                    ind.next = head2;
                    head2 = head2.next;
                    ind = ind.next;
                }
                else{
                    //head2 is next lowest dat and i next is pointing to it
                    //move head2 and iterator over
                    head2 =head2.next;
                    ind = ind.next;
                }
    
            }  
            return sorted;
        }
    
    2|
    Permalink
  • clarify_me101
    1 week ago+ 0 comments

    Since the maximum number of elements is only 1000, you can use a simple trick here, 1) first get all the elements into a LIST and then sort it 2) afterwards you can create a new LInkedList from the sorted list

    def mergeLists(head1, head2):
        my_list = []
        node = head1
        while node is not None:
            my_list.append(node.data)
            node = node.next
        node2 = head2
        while node2 is not None:
            my_list.append(node2.data)
            node2 = node2.next
        my_list.sort()
        
        ll3 = SinglyLinkedList()
        for num in my_list:
            ll3.insert_node(num)
            
        return ll3.head
    
    1|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature