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.
  1. Prepare
  2. Data Structures
  3. Linked Lists
  4. Merge two sorted linked lists
  5. Discussions

Merge two sorted linked lists

Sort by

recency

|

985 Discussions

|

  • polagorge
     + 0 comments
        static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {

         SinglyLinkedListNode newList = null;

    if(head1.data < head2.data){
        newList = new SinglyLinkedListNode(head1.data);
        head1 = head1.next;
    }else{
        newList = new SinglyLinkedListNode(head2.data);
        head2 = head2.next;
    }

    var head = newList;

    while(head1 != null && head2 != null){

        if(head1.data < head2.data){
            newList.next = new SinglyLinkedListNode(head1.data);
            head1 = head1.next;
        }else{
            newList.next = new SinglyLinkedListNode(head2.data);
            head2 = head2.next;
        }
        newList = newList.next;
    }
    newList.next = (head1 != null) ? head1 : head2;


    return head;
}

  • gfigueroam
     + 0 comments

    Hi all, here my recursive solution in Java 8.

        static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
        if(head1== null && head2== null)
            return null;
        if(head1 == null)
            return head2;
        if(head2 == null) {
            return head1;
        }
        SinglyLinkedListNode result = null;
        if(head1.data< head2.data){
            result = head1;
            result.next = mergeLists(head1.next, head2);
        } else {
            result = head2;
            result.next = mergeLists(head1, head2.next);
        } 
        
        return result;
    }

  • jeelpatel779
     + 0 comments
        SinglyLinkedListNode* head=new SinglyLinkedListNode(0);
    SinglyLinkedListNode* temp=head;
    
    while(head1!=nullptr && head2!=nullptr){        
        if(head1->data<=head2->data){
            SinglyLinkedListNode* newNode=new SinglyLinkedListNode(head1->data);
            temp->next=newNode;
            head1=head1->next;
        }else {
            SinglyLinkedListNode* newNode=new SinglyLinkedListNode(head2->data);
            temp->next=newNode;
            head2=head2->next;
        }temp=temp->next;
    }
    while(head1!=nullptr){
        SinglyLinkedListNode* newNode=new SinglyLinkedListNode(head1->data);
        head1=head1->next;
        temp->next=newNode;
        temp=temp->next;
    }
    while(head2!=nullptr){
        SinglyLinkedListNode* newNode=new SinglyLinkedListNode(head2->data);
        head2=head2->next;
        temp->next=newNode;
        temp=temp->next;
    }head=head->next;
    return head;
}

  • mdsanz
     + 0 comments

    My Java 8 Solution

    static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
        SinglyLinkedListNode mergedLists = new SinglyLinkedListNode(0);
        SinglyLinkedListNode current = mergedLists;
        
        while (head1 != null && head2 != null) {
            if (head1.data <= head2.data) {
                current.next = head1;
                head1 = head1.next;
            } else {
                current.next = head2;
                head2 = head2.next;
            }
            current = current.next;
        }        
        
        if (head1 != null) {
            current.next = head1;
        } else {
            current.next = head2;
        }
        
        return mergedLists.next;
    }

  • emhhacker
     + 0 comments

    My Java solution with linear time complexity and constant space complexity:

    static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
        //handle edge cases where there is no other list to merge
        if(head1 == null) return head2;
        if(head2 == null) return head1;
        
        //determine the new head of the merged linked list
        SinglyLinkedListNode head;
        if(head1.data <= head2.data){
            head = head1;
            head1 = head1.next;
        }
        else{
            head = head2;
            head2 = head2.next;
        }
        
        //iterate through both linked lists, sorting asc
        SinglyLinkedListNode curr = head;
        while(head1 != null && head2 != null){
            if(head1.data <= head2.data){
                curr.next = head1;
                head1 = head1.next;
            }
            else{
                curr.next = head2;
                head2 = head2.next;
            }
            curr = curr.next;
        }
        
        //append any extra vals to the merged linked list
        if(head1 != null) curr.next = head1;
        else if(head2 != null) curr.next = head2;
        
        return head;
    }