每天一个小算法还是有点没时间，尽量抽出时间写一写。
今天是合并有序的链表，对单链表有点忘了，尤其是指针指来指去的，有点晕，幸好基础还算好，想了想还是能想回来。
代码使用随机数函数生成一个链表，然后对链表排序，最后合并链表并打印，删除链表的函数于算法无关紧要，所以未实现^_^。
在Linux/g++下编译运行成功。
合并思路：和合并数组有些类同，比较两个节点的元素大小然后将小的摘下来尾插到链表bList中，然后指针指向下一个节点，最后直接把非空的链表合并到bList的末尾。
1 #include2 #include 3 #include 4 typedef struct Node 5 { 6 int data; 7 Node* next; 8 }Node, *List; 9 10 void sortList(List aList) //对随机数字链表排序 11 { 12 if(aList == NULL) 13 return; 14 15 List pT = aList->next; 16 aList->next = NULL; 17 while ( pT != NULL ) 18 { 19 List pr = pT; 20 List pU = pT; 21 List pN = NULL; 22 while ( pU->next != NULL ) 23 { 24 if ( pr->data <= pU->next->data ) 25 { 26 pN = pU; 27 pr = pU->next; 28 } 29 30 pU = pU->next; 31 } 32 33 if ( pN != NULL ) 34 { 35 pN->next = pr->next; 36 } 37 else 38 { 39 pT = pT->next; 40 } 41 pr->next = aList->next; 42 aList->next = pr; 43 } 44 } 45 46 List createList(int num) //随机生成数字，构造链表 47 { 48 List aList = (List)malloc(sizeof(Node)); 49 aList->next = NULL; 50 aList->data = 0; 51 Node* qT = aList; 52 53 // srand((int)time(0)); 54 for ( int i=0; i< num; ++i) 55 { 56 Node* pTN = (Node*)malloc(sizeof(Node)); 57 pTN->data = rand()%100; 58 pTN->next = NULL; 59 qT->next = pTN; 60 qT = pTN; 61 } 62 sortList(aList); 63 return aList; 64 } 65 66 void printList(List aList) //打印链表 67 { 68 if ( aList == NULL || aList->next == NULL ) 69 return; 70 71 Node* pT = aList->next; 72 printf("element of list:\n\t"); 73 while( pT != NULL ) 74 { 75 printf("%d ", pT->data); 76 pT = pT->next; 77 } 78 79 printf("\n"); 80 } 81 82 void deleteList(List aList) //删除链表 83 {} 84 85 void mergeList(List aList, List bList) //合并链表 86 { 87 if ( aList == NULL || bList == NULL ) 88 return; 89 90 Node* pA = aList->next; 91 Node* pB = bList->next; 92 Node* pT = NULL; 93 Node* pN = bList; 94 bList->next = NULL; 95 delete aList; 96 97 while ( pA != NULL && pB != NULL ) 98 { 99 if ( pA->data < pB->data )100 {101 pT = pA->next;102 pA->next = pN->next;103 pN->next = pA;104 pN = pN->next;105 pA = pT;106 }107 else108 {109 pT = pB->next;110 pB->next = pN->next;111 pN->next = pB;112 pN = pN->next;113 pB = pT; 114 }115 }116 117 if ( pA == NULL )118 {119 pN->next = pB;120 }121 122 if ( pB == NULL )123 {124 pN->next = pA;125 }126 }127 128 int main(int argc, char const *argv[])129 {130 srand((int)time(0));131 List aList = createList(5);132 List bList = createList(7);133 printList(aList);134 printList(bList);135 136 mergeList(aList, bList);137 printList(bList);138 139 deleteList(bList);140 141 return 0;142 }