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++;
}
}
}
Sunday, August 28, 2011
Merging two sorted linked lists
Subscribe to:
Post Comments (Atom)
if(list2 == null){//if list2 is null, simply return list1
ReplyDeletereturn 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
}
thank u
ReplyDeleteDo you think that you should include the equality case too?
ReplyDeleteFor eg - 1->2->3 and 2->3->4
the result will be this
1->2->2->3->4
which is wrong.
then what will be he coreect code?
DeleteNode* MergeLists(Node *headA, Node* headB)
Delete{
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
}