每天一个小算法（2）----合并两个有序链表

每天一个小算法还是有点没时间，尽量抽出时间写一写。

今天是合并有序的链表，对单链表有点忘了，尤其是指针指来指去的，有点晕，幸好基础还算好，想了想还是能想回来。

代码使用随机数函数生成一个链表，然后对链表排序，最后合并链表并打印，删除链表的函数于算法无关紧要，所以未实现^_^。

在Linux/g++下编译运行成功。

合并思路：和合并数组有些类同，比较两个节点的元素大小然后将小的摘下来尾插到链表bList中，然后指针指向下一个节点，最后直接把非空的链表合并到bList的末尾。

  1 #include <stdio.h>
  2 #include <time.h>
  3 #include <stdlib.h>
  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:
	");
 73     while( pT != NULL )
 74     {
 75         printf("%d ", pT->data);
 76         pT = pT->next;
 77     }
 78 
 79     printf("
");
 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         else
108         {
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 }

每天一个小算法（2）----合并两个有序链表

相关推荐