Discussion on Merge two sorted linked lists Challenge

Sort 679 Discussions, By:

Dark_Knight19 5 years ago+ 0 comments

Here is a simple recursive solution that passes both test cases!

if((headA==NULL)&&(headB==NULL)
    return NULL;
if((headA!=NULL)&&(headB==NULL))
    return headA;
if((headA == NULL)&&(headB!=NULL))
    return headB;
if(headA->data < headB->data)
    headA->next = MergeLists(headA->next, headB);
else if(headA->data > headB->data)
{
    Node* temp = headB;
    headB = headB->next;
    temp->next = headA;
    headA = temp;
    headA->next = MergeLists(headA->next, headB);
}
return headA;

}

calvin_k_stone 5 years ago+ 0 comments

Heres the recursive python 2 / 3 solution I came to.

def MergeLists(headA, headB):
  if headA is None and headB is None:
    return None
  
  if headA is None:
    return headB

  if headB is None:
    return headA
  
  if headA.data < headB.data:
    smallerNode = headA
    smallerNode.next = MergeLists(headA.next, headB)
  else:
    smallerNode = headB
    smallerNode.next = MergeLists(headA, headB.next)
  
  return smallerNode

RodneyShag 4 years ago+ 0 comments

O(1) space complexity Java solution

From my HackerRank solutions.

Runtime: O(n +m)
Space Complexity: O(1)

Any recursive solution will take at least O(n+m) space due to O(n+m) recursive calls. Try to do it iteratively for a more space efficient solution.

Node MergeLists(Node currA, Node currB) {
    if (currA == null) {
        return currB;
    } else if (currB == null) {
        return currA;
    }
    
    /* Find new head pointer */
    Node head = null;
    if (currA.data < currB.data) {
        head = currA;
        currA = currA.next;
    } else {
        head = currB;
        currB = currB.next;
    }
    
    /* Build rest of list */
    Node n = head;
    while (currA != null && currB != null) {
        if (currA.data < currB.data) {
            n.next = currA;
            currA = currA.next;
        } else {
            n.next = currB;
            currB = currB.next;
        }
        n = n.next;
    }
    
    /* Attach the remaining elements */
    if (currA == null) {
        n.next = currB;
    } else {
        n.next = currA;
    }

    return head;
}

Let's try an example

List A: 1 -> 4 -> null
List B: 2 -> null

Created: null

Now the code labeled Find new head pointer will give us the following result:

List A: 4 -> null
List B: 2 -> null

Created: 1 -> null

The code labeled Build rest of list will then give us:

List A: 4 -> null
List B: null

Creaetd: 1 -> 2

Finally, the code labeled Attach the remaining elements will complete our list:

List A: null
List B: null

Created: 1 -> 2 -> 4

Let me know if you have any questions.

imaginationsuper 5 years ago+ 0 comments

Node MergeLists(Node headA, Node headB) {
     // This is a "method-only" submission. 
     // You only need to complete this method 
    if (headA == null)
        return headB;
    else if (headB == null)
        return headA;
    else if (headA.data <= headB.data){
        headA.next = MergeLists(headA.next, headB);
        return headA;
    } else {
        headB.next = MergeLists(headA, headB.next);
        return headB;
    }
}

possen 4 years ago+ 0 comments

This is a fairly compact and efficent non-recursive solution.

def MergeLists(nodeA, nodeB):
    mergedHead = Node() # dummy node so can be handled the same
    merged = mergedHead

    while nodeA != None or nodeB != None:
        if nodeA == None:
            merged.next = nodeB
            break
        elif nodeB == None:
            merged.next = nodeA
            break
        else:
            if nodeA.data < nodeB.data:
                merged.next = nodeA
                nodeA = nodeA.next
            else:
                merged.next = nodeB
                nodeB = nodeB.next
        merged = merged.next

    return mergedHead.next

Load more conversations