剑指offer 合并两个排序的链表

题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

代码（迭代版本）：

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* Merge(ListNode* phead1, ListNode* phead2)
12     {
13         if(phead1 == NULL)
14             return phead2;
15         if(phead2 == NULL)
16             return phead1;
17         ListNode* head = new ListNode(NULL);
18         ListNode* pre = head;
19         pre->next = phead1;
20         while(pre->next != NULL && phead2 != NULL){ //以pre为基准将phead2填入pre中
21             if(pre->next->val > phead2->val){
22                 ListNode* arg = new ListNode(phead2->val); //用来存储当前较小结点
23                 ListNode* temp = pre->next; //常规链表插入操作
24                 pre->next = arg;
25                 pre->next->next = temp;
26                 phead2 = phead2->next;
27             }
28             pre = pre->next; //将基准链表向后移动
29         }
30         if(phead2 != NULL) //如果phead2尚未插入完毕，则将其全部填入pre后
31             pre->next = phead2;
32         head = head->next;
33         return head;
34     }
35 };

代码（递归版本）：

 1 public ListNode Merge(ListNode list1,ListNode list2) {
 2        if(list1 == null){
 3            return list2;
 4        }
 5        if(list2 == null){
 6            return list1;
 7        }
 8        if(list1.val <= list2.val){
 9            list1.next = Merge(list1.next, list2);
10            return list1;
11        }else{
12            list2.next = Merge(list1, list2.next);
13            return list2;
14        }       
15    }

我的笔记：迭代版本的实现以一条链表为基准，将另一条链表插入其中。

注意：1. 在对链表进行操作时，例如：temp = pre->next ;，是将 pre->next 的地址赋值给temp,而 *temp = *pre 的话是将*pre完全复制给*temp；区别在于，前者在对temp进行操作时，同时也会更改pre->next的值，而后者在对*temp操作时，*pre是不会受到影响的。是地址与指针的区别。