合并有序的链表（这里是升序），只是改变指针的方向O(n)，也是一道超经典的题目，完整实现如下：
# include <stdio.h> # include <malloc.h> typedef struct LNode{ int data; struct LNode *next; }LNode, *LinkList; /** * 采用数组a[]来初始化链表，数组的长度为length;head指向了头节点。 */ LinkList CreatList(int a[], int length) { LinkList head = (LinkList)malloc(sizeof(LNode)); head->next = NULL; int index; LinkList temp; for (index = 0; index < length; index ++) { temp = (LinkList)malloc(sizeof(LNode)); temp->data = a[index]; temp->next = head->next; head->next = temp; } return head; } /** * 将升序链表list1,list2合并为list3，只改变list1与list2的指针方向 */ LinkList Merge(LinkList list1, LinkList list2) { LinkList ptr1 = list1->next; LinkList ptr2 = list2->next; LinkList ptr3 = (LinkList)malloc(sizeof(LNode)); LinkList begin = ptr3; // ptr3 = ptr3->next; while(ptr1 && ptr2) { if (ptr1->data < ptr2->data) { ptr3->next = ptr1; ptr3 = ptr1; ptr1 = ptr1->next; } else { ptr3->next = ptr2; ptr3 = ptr2; ptr2 = ptr2->next; } } if (ptr1) { ptr3->next = ptr1; // ptr3 = ptr1; } if (ptr2) { ptr3->next = ptr2; // ptr3 = ptr2; } return begin; } int main() { int a1[] = {5,3,1}; int a2[] = {8,6,4,2,0}; LinkList list1 = CreatList(a1,3); LinkList list2 = CreatList(a2,5); LinkList list3 = Merge(list1,list2); PrintList(list3);
