《剑指offer》面试题17—合并两个排序链表

题目：输入两个递增排顺序的链表，合并这两个链表并使合并后的链表仍是递增排序的。

重点：

1.代码鲁棒性：要判断输入的两个链表都为NULL；其中一个链表为NULL的情况。

2.用递归实现，注意递归的思路。

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 struct Node
 6 {
 7     int val;
 8     Node* next;
 9 };
10 
11 
12 void PrintLink(Node* phead)
13 {
14     Node* p = phead;
15     while(p != NULL)
16     {
17         int temp = p->val;
18         cout<<temp<<endl;
19         p = p->next;
20     }
21 }
22 
23 Node* Merge(Node* phead1, Node* phead2)
24 {
25     if(phead1 == NULL && phead2 == NULL) return NULL;
26     else if(phead1 == NULL && phead2 != NULL) return phead2;
27     else if(phead1 != NULL && phead2 ==NULL) return phead1;
28     else
29     {
30         Node* pselected;
31         if(phead1->val < phead2->val)
32         {
33             pselected = phead1;
34             pselected->next = Merge(phead1->next,phead2);
35         }
36         else
37         {
38             pselected = phead2;
39             pselected->next = Merge(phead1,phead2->next);
40         }
41     return pselected;
42     }
43 
44 }
45 
46 int main()
47 {
48     int n;
49    // while(scanf("%d",&n)!=EOF)
50   cin>>n;
51         Node * head1;
52         if(!n)
53         head1=NULL;
54         else
55         head1=new Node();
56         Node * p=head1;
57         for(int i=0;i<n;++i)
58         {
59             scanf("%d",&p->val);
60             if(i==n-1)
61             {
62                 p->next=NULL;
63                 break;
64             }
65             p->next=new Node();
66             p=p->next;
67         }
68         PrintLink(head1);
69 
70         scanf("%d",&n);
71         Node * head2;
72         if(!n)
73         head2=NULL;
74         else
75         head2=new Node();
76         p=head2;
77         for(int i=0;i<n;++i)
78         {
79             scanf("%d",&p->val);
80             if(i==n-1)
81             {
82                 p->next=NULL;
83                 break;
84             }
85             p->next=new Node();
86             p=p->next;
87         }
88         PrintLink(head2);
89         Node * newhead=Merge(head1,head2);
90         PrintLink(newhead);
91     return 0;
92 }

View Code