一,题目
两个非降序链表的并集,1->2->3
和 2->3->5 并为 1->2->3->5。另外只能输出结果,不能修改两个链表的数据。
二,递归解法
#include <iostream> using namespace std; struct Node { int data; Node * next; }; Node * MergeRecursive(Node *head1 , Node *head2) { if ( head1 == NULL ) return head2 ; if ( head2 == NULL) return head1 ; Node *head = new Node() ; if ( head1->data < head2->data ) { head = head1 ; head->next = MergeRecursive(head1->next,head2); } else { head = head2 ; head->next = MergeRecursive(head1,head2->next); } return head ; } Node *creatLink(int a[],int n) { Node *head=new Node(); head->data=a[0]; Node *tail=head; head->next=NULL; for(int i=1;i<n;++i) { Node *temp=new Node(); temp->data=a[i]; temp->next=NULL; tail->next=temp; tail=tail->next; } return head; } int main() { int a[]={1,2,4,6,7}; int b[]={2,3,5,7,8}; Node *headA=creatLink(a,5); Node *headB=creatLink(b,5); Node *headResult= MergeRecursive(headA , headB); while(headResult) { cout<<headResult->data<<" "; headResult=headResult->next; } }