将2个分别有序的链表合并成一个链表,并且合并后的链表依然有序。
方法:初始化一个头结点head,然后比较list1,和list2链表的第一个节点,选择比较小的连接到head上去,如此往复。
#include "stdafx.h" #include<iostream> #include<queue> using namespace std; typedef struct node{ int data; struct node *next; }Node,*List; List createList(int N,int multi) { List head = (List)malloc(sizeof(Node)); head->data = 0; head->next=NULL; int count = 0; List p = head; while(count<N) { count++; List s = (List)malloc(sizeof(Node)); s->data = count*multi; s->next = NULL; p->next = s; p = s; } return head; } void traverse(List head) { if(head == NULL) { return; } List p = head->next; while(p) { cout<<p->data<<" "; p = p->next; } cout<<endl; } List unionList(List list1,List list2) { if(list1 == NULL||list1->next==NULL) return list2; if(list2 == NULL||list1->next==NULL) return list1; list1 = list1->next; list2 = list2->next; List head = (List)malloc(sizeof(Node)); List p = NULL; if(list1!=NULL && list2!=NULL)//初始化第一个节点 { if(list1->data<=list2->data) { head->next = list1; list1 = list1->next; }else{ head->next = list2; list2 = list2->next; } } p = head->next; while(list1!=NULL && list2!=NULL)//主体部分 { if(list1->data<=list2->data) { p->next = list1; list1 = list1->next; p = p->next; }else{ p->next = list2; list2 = list2->next; p = p->next; } } while(list1 != NULL)//如果list2已经完了,list1还有剩余 { p->next = list1; list1 = list1->next; p = p->next; } while(list2 != NULL)//如果list1已经完了,list2还有剩余 { p->next = list2; list2 = list2->next; p = p->next; } return head; } int main() { int N = 10; List head1 = createList(N,1); List head2 = createList(N,2); traverse(head1); traverse(head2); List head = unionList(head1,head2); traverse(head); getchar(); return 0; }