题目要求：
两个非降序链表的并集，1->2->3和2->3->5合并为1->2->3->5.
另外只能输出结果，不能修改两个链表的数据。
题目分析：
1.不能修改原链表数据：即，输出1->2->3->5后，原来的两个链表还是1->2->3和2->3->5。因此输出的这些结点都需要重新申请空间存放，不能使用原来的结点。
2.去掉相同值的结点。即，如果head1为1->2->2->3,head2为NULL，输出都不是head1，而是1->2->3.
代码实现：
#includeusing namespace std;typedef struct ListNode{ struct ListNode *next; int data;}ListNode;ListNode *MergeTwoList(ListNode *h1,ListNode *h2);void initList(ListNode **head1,ListNode **head2);int main(void){ ListNode *head1,*head2; ListNode *mergeList; initList(&head1,&head2); mergeList = MergeTwoList(head1,head2); while(mergeList) { cout << mergeList->data << "->"; mergeList = mergeList->next; } cout << "NULL" << endl; return 0;}ListNode *Handle(ListNode *h){ if(h==NULL) return NULL; int last = h->data; ListNode *tmp = new ListNode; tmp->data = h->data; tmp->next = NULL; ListNode *head = tmp; h = h->next; ListNode *tmp2; while(h) { if(last!=h->data) { tmp2 = new ListNode; tmp2->data = h->data; tmp2->next = NULL; tmp->next = tmp2; tmp = tmp2; last = tmp2->data; } h = h->next; } return head;}ListNode *MergeTwoList(ListNode *h1,ListNode *h2){ if(h1==NULL) return Handle(h2); if(h2==NULL) return Handle(h1); ListNode *head,*tmp,*tmp1; int last; if(h1->data < h2->data) { tmp = new ListNode; tmp->data = h1->data; last = h1->data; tmp->next = NULL; head = tmp; h1 = h1->next; } else { tmp = new ListNode; tmp->data = h2->data; last = h2->data; tmp->next = NULL; head = tmp; h2 = h2->next; } while(h1!=NULL && h2!=NULL) { if(h1->data < h2->data) { if(h1->data!=last) { tmp1 = new ListNode; tmp1->data = h1->data; last = h1->data; tmp1->next = NULL; tmp->next = tmp1; tmp = tmp1; } h1 = h1->next; } else { if(h2->data!=last) { tmp1 = new ListNode; tmp1->data = h2->data; last = h2->data; tmp1->next = NULL; tmp->next = tmp1; tmp = tmp1; } h2 = h2->next; } } if(h1!=NULL) tmp->next = Handle(h1); if(h2!=NULL) tmp->next = Handle(h2); return head;}void initList(ListNode **head1,ListNode **head2){ ListNode *tmp = new ListNode; tmp->data = 1; *head1 = tmp; tmp = new ListNode; tmp->data = 2; (*head1)->next = tmp; ListNode *tmp1 = new ListNode; tmp1->data = 2; tmp1->next = NULL; tmp->next = tmp1; //----------------------------- tmp = new ListNode; tmp->data = 1; *head2 = tmp; tmp = new ListNode; tmp->data = 3; (*head2)->next = tmp; tmp1 = new ListNode; tmp1->data = 5; tmp1->next = NULL; tmp->next = tmp1;}