首页 > 代码库 > 线性时间将两个有序链表合成一个有序链表(constant additional space)
线性时间将两个有序链表合成一个有序链表(constant additional space)
description:
given two sorted singly list, merge them into one using constant additional space
algorithm:
we will reference the two linked list as list1 and list2 for convenience,
since list1 is sorted,just find the right position for each element in list2,
detailed comments are added to the following code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 | #include<iostream> #include<cstdio> #include<string.h> #include<string> #include<cstring> #include<algorithm> using namespace std; class Node{ public : int value; Node* Next; Node( int v_ = 0, Node* Next_ = NULL):value(v_),Next(Next_){} }; /*Node* Merge2(Node* head1, Node* head2) { Node* res,*ret; if(head1 == NULL) return head2; if(head2 == NULL) return head1; Node* p = head1; Node* q = head2; if(p->value < q->value) { res = p; p = p->Next; } else { res = q; q = q->Next; } ret = res; while(p && q) { if(p->value < q->value) { res->Next = p; res = p; p = p->Next; } else { res->Next = q; res = q; q = q->Next; } } while(p) { res->Next = p; res = p; p = p->Next; } while(q) { res->Next = q; res = q; q = q->Next; } return ret; }*/ Node* Merge2(Node*p1,Node*p2){ if (p1 == NULL) return p2; if (p2 == NULL) return p1; Node *tmpp1 = p1,*tmpp2 = p2; Node*head; bool first = true ; /*core optimization: if tmpp2 find its place in list1, then tmpp2->next must be after its position,so both list1 and list2 are enumerated only once, which implements linear algorithm*/ while (tmpp1 != NULL && tmpp2 != NULL){ Node* tmpformer = NULL; while (tmpp1 != NULL && tmpp2->value > tmpp1->value){ tmpformer = tmpp1; tmpp1 = tmpp1->Next; } if (tmpp1 == NULL){ tmpformer->Next = tmpp2; if (first){ first = false ; head = p1; } break ; } //tmpp2的value值比tmpp1的value值小但是比tmpformer的value值大 Node* tmprecordp2 = tmpp2->Next; tmpp2->Next = tmpp1; if (tmpformer != NULL){ tmpformer->Next = tmpp2; if (first){ first = false ; head = p1; } } else { if (first){ first = false ; head = p2; } } tmpp2 = tmprecordp2; } return head; } int main(){ Node* p1[10], *p2[10]; memset (p1,0, sizeof (p1)); memset (p2,0, sizeof (p2)); int a[25] = {1,3,6,7,8,9,56,67,211,763,2,4,5,10,11,12,13,300,500,800}; /*initalization*/ for ( int i = 0; i < 10; ++i){ p1[i] = new Node(a[i]); } for ( int i = 0; i < 10; ++i){ p2[i] = new Node(a[10+i]); } Node* pp1,*pp2; for ( int i = 0; i < 9; ++i){ // cout << &(p1[i]->Next) << endl; p1[i]->Next = p1[i+1]; } for ( int i = 0; i < 9; ++i){ p2[i]->Next = p2[i+1]; } pp1 = p1[0]; while (pp1 != NULL){ cout << pp1->value << ‘\t‘ ; pp1 = pp1->Next; } cout << endl; pp2 = p2[0]; while (pp2 != NULL){ cout << pp2->value << ‘\t‘ ; pp2 = pp2->Next; } cout << endl; /*initialization end*/ Node* res = Merge2(p1[0],p2[0]); while (res!=NULL){ cout << res->value << endl; res = res->Next; } for ( int i = 0; i < 10; ++i){ delete p1[i]; } for ( int i = 0; i < 10; ++i){ delete p2[i]; } return 0; } |
key points:
1.pay special attention to keep head pointer, which is easily lost,
my solution is to set a flag bool variance, which is linear complexity but somewhat inefficient
perhaps it has potential to improve
2.avoid misorder of pointer
3.special condition: if (p1 == NULL) return p2;
if(p2 == NULL ) return p1;
4.when search for the postion for a certain element in list1, note that it might be above any element in list1 so tmpp1 might reach its end(value equals NULL) during search