Merge two sorted linked lists

Sort by

recency

|

229 Discussions

|

  • + 0 comments

    C# solution after consulting geeksforgeeks when I got stuck

    static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
            
            if (head1 is null) return head2;
            if (head2 is null) return head1;
            
            if (head1.data <= head2.data)
            {
                head1.next = mergeLists(head1.next, head2);
                return head1;
            }
            else
            {
              head2.next = mergeLists(head1, head2.next);
              return head2; 
            }
        }
    
  • + 0 comments

    C#, test case two fails. It seems there is 1 test case, for which the first linked list is 8 ints. The next set of ints for list 2 are unordered it seems. All of my other test cases pass.

  • + 0 comments

    the explanation part with sample had mistake ,

    Explanation

    The first linked list is: 1 -> 3 -> 7 ->NULL The second linked list is: 3->4->NULL Hence, the merged linked list is: 1->2->3->3->4->NULL where is the 7 gone from list 1 ?

  • + 0 comments

    Bit hacky but...

    def mergeLists(head1, head2):
        
        merged = SinglyLinkedList()
        
        while head1 is not None and head2 is not None:
            if head1.data < head2.data:
                merged.insert_node(head1.data)
                head1 = head1.next
            else:
                merged.insert_node(head2.data)
                head2 = head2.next
                
        if head1 is not None:
            while head1 is not None:
                merged.insert_node(head1.data)
                head1 = head1.next
                
        if head2 is not None:
            while head2 is not None:
                merged.insert_node(head2.data)
                head2 = head2.next
                
        return merged.head
    
  • + 0 comments

    Not very clean, but non-recursive solution that uses given class in js:

    function mergeLists(head1, head2) {
        if(head1 === null) return head2;
        if(head2 === null) return head1;
        let returnNode;
        if(head1.data < head2.data){
            returnNode = new SinglyLinkedListNode(head1.data);
            head1 = head1.next;
        }else {
            returnNode = new SinglyLinkedListNode(head2.data);
            head2 = head2.next
        }
        let currentNode = new SinglyLinkedListNode();
        returnNode.next = currentNode;
        while(head1 != null && head2 != null){
            if(head1.data <= head2.data){
                currentNode.data = head1.data;
                head1 = head1.next;
                currentNode.next = new SinglyLinkedListNode();
                currentNode = currentNode.next;
            }else if(head1.data > head2.data){
                currentNode.data = head2.data;
                head2 = head2.next;
                currentNode.next = new SinglyLinkedListNode();
                currentNode = currentNode.next;
            }
        }
        if(head1 === null && head2 != null){
            currentNode.data = head2.data;
            currentNode.next = head2.next;
        };
        if(head2 === null && head1 != null){
            currentNode.data = head1.data;
            currentNode.next = head1.next;
        };
        
        return returnNode;
    }