这两天时间比较充裕，就多写几道吧，现在是农历八月十五晚上八点多，外面皓月当空，夜色如水，搞得我都诗兴大发了，这真是窗前明月光，疑是地上霜，举头望明月，低头思故乡啊。。。

好了不扯皮了，今天给大家带来的是第21题，也是一道比较简单的题目，考察的点很单一，就是链表这种数据结构的基本操作，还是那句话，数据结构这门课大家一定要学好啊，计算机相关专业的一定要仔细听讲，认真做题，非计算机专业的自己也应该找本书来钻研一下，个人认为学习数据结构和算法是比学习编程语言更重要的。因为语言嘛，就是一种表示方式，而真正的内容是数据结构和算法组成的，所以我也是再三强调，这个东西含糊不得。好了，上题

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

没错，题目就这么一句话，就是让你把两个有序链表合并为一个，要求就地合并，不能另外开辟存储空间。这个东西如果你学过归并排序这种算法的话那简直就是小儿科了，归并排序是排序方法的一种，基本思想就是给定两个有序数组，然后比较它们的首元素，把小的加入新数组，同时在比较下一对元素的大小，把小的放入新数组，直到一个数组为空了，把另一个剩下的拷贝到新数组里。这个我就不细讲了，不明白的可以百度一下归并排序。

了解了归并排序原理，那就没什么好说的了，代码如下

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

		ListNode nul(0);
		ListNode* res=&nul;
		ListNode* res2=res;
		while(l1!=NULL && l2!=NULL)
		{
			if(l1->val < l2->val)
			{
				res=res->next=l1;l1=l1->next;
			}
			else
			{
				res=res->next=l2;l2=l2->next;
			}
		}
		while(l1!=NULL)
		{
			res=res->next=l1;l1=l1->next;
		}
		while(l2!=NULL)
		{
			res=res->next=l2;l2=l2->next;
		}
		return res2->next;
        
    }
};