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

|

984 Discussions

|

  • 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;
    }

  • calancea_bianca1
     + 0 comments

    def mergeLists(head1, head2):

      new_list=SinglyLinkedList()

current1=head1
current2=head2

while current1 and current2:
    if current1.data==current2.data:
        new_list.insert_node(current1.data)
        new_list.insert_node(current2.data)
        current1=current1.next
        current2=current2.next
    elif current1.data < current2.data:
        new_list.insert_node(current1.data)
        current1=current1.next
    elif current2.data < current1.data:
        new_list.insert_node(current2.data)
        current2=current2.next

while current1:
    new_list.insert_node(current1.data)
    current1=current1.next

while current2:
    new_list.insert_node(current2.data)
    current2=current2.next

return new_list.head