Sunday, August 28, 2011

Merging two sorted linked lists


Node* MergeLists(Node* list1, Node* list2){
    Node* mergedList;
    if(list1 == null && list2 ==null){//if both are null, return null
        return null;
    }
    if(list1 == null){//if list1 is null, simply return list2
        return list2;
    }
    if(list2 == null){//if list2 is null, simply return list1
        return list1;
    }
    if(list1.data < list2.data){//initialize mergedList pointer to list1 if list1's data is lesser
        mergedList = list1;
    }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
        mergedList = list2;
    }
    while(list1!=null && list2!=null){
        if(list1.data < list2.data){
            mergedList->next = list1;
            list1 = list1->next;
        }else{
            mergedList->next = list2;
            list2 = list2->next;
        }
    }
    if(list1 == null){//remaining nodes of list2 appended to mergedList when list1 has reached its end.
        mergedList->next = list2;
    }else{//remaining nodes of list1 appended to mergedList when list2 has reached its end
        mergedList->next = list1;
    }
    return mergedList;
}

Merging two Sorted Arrays

public void merge(int[] A, int[] B, int[] C) { int i, j, k, m, n; i = 0; j = 0; k = 0; m = A.length; n = B.length; while (i < m && j < n) { if (A[i] <= B[j]) { C[k] = A[i]; i++; } else { C[k] = B[j]; j++; } k++; } if (i < m) { for (int p = i; p < m; p++) { C[k] = A[p]; k++; } } else { for (int p = j; p < n; p++) { C[k] = B[p]; k++; } } }

5 comments:

  1. if(list2 == null){//if list2 is null, simply return list1
    return list1;
    }
    if(list1.data < list2.data){//initialize mergedList pointer to list1 if list1's data is lesser
    mergedList = list1;
    }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
    mergedList = list2;
    }

    this should be changed to:

    if(list2 == null){//if list2 is null, simply return list1
    return list1;
    }
    if(list1.data < list2.data){//initialize mergedList pointer to list1 if list1's data is lesser
    mergedList = list1;
    list1 = list1->next; //<--change here
    }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
    mergedList = list2;
    list2 = list2->next; //<--change here
    }

    ReplyDelete
  2. Do you think that you should include the equality case too?

    For eg - 1->2->3 and 2->3->4
    the result will be this
    1->2->2->3->4

    which is wrong.

    ReplyDelete
    Replies
    1. then what will be he coreect code?

      Delete
    2. Node* MergeLists(Node *headA, Node* headB)
      {
      Node *mergelist = NULL;
      Node *mergehead = NULL;

      if (headA == NULL && headB ==NULL)
      return NULL;
      if (headA == NULL)
      return headB;
      if (headB == NULL)
      return headA;

      if (headA->data < headB->data){

      mergelist = headA;
      headA = headA->next;
      }
      else{
      mergelist = headB;
      headB = headB->next;
      }
      mergehead = mergelist;

      while ((headA != NULL) && (headB != NULL)){
      if ((headA->data) < (headB->data)){
      mergelist->next = headA;
      headA = headA->next;
      }else{
      mergelist->next = headB;
      headB = headB->next;
      }
      mergelist = mergelist ->next;
      }

      if (headA == NULL){
      mergelist ->next = headB;
      }
      else{
      mergelist ->next = headA;
      }


      return mergehead;


      // This is a "method-only" submission.
      // You only need to complete this method
      }

      Delete