#include <iostream> using namespace std; struct LinkList { int data; LinkList *next; }; LinkList* createList() { LinkList *head = NULL, *p, *q; int data; cin >> data; while(data) { p = new LinkList; p->data = data; p->next = NULL; if(head == NULL) { head = p; q = head; } else { q->next = p; q = p; } cin >> data; } return head; } // 合并后的链表放在pLinkList中 void merge(LinkList *&pLinkList, LinkList *qLinkList) { LinkList *pre, *p, *q; pre = NULL; p = pLinkList; q = qLinkList; while(p != NULL && q != NULL) { if(p->data < q->data) { pre = p; p = p->next; } else { // 如果p第一个结点大于q，则改变合并后头结点为q if(pre == NULL) { pLinkList = q; } else { pre->next = q; } pre = q; q=q->next; pre->next = p; } } // 最后不要忘了qLinkList剩余的大结点 if(q != NULL) { pre->next = q; } } void print(LinkList *l) { LinkList *p = l; while(p != NULL) { if(p->next == NULL) { cout << p->data; break; } cout << p->data << " -> "; p = p->next; } cout << endl; } int main() { cout << "Please enter pLinkList: "; LinkList *pLinkList = createList(); print(pLinkList); cout << "\nPlease enter pLinkList: "; LinkList *qLinkList = createList(); print(qLinkList); merge(pLinkList, qLinkList); cout << "\nThe merge LinkList is: \n"; print(pLinkList); return 0; }