/首先判断两个链表是否为空，如果其中一个为空则返回另一个链表的头结点，若都是空，则返回空；其次比较两个数组，选取较小的头结点作为新链表的头结点，然后依次链接比较其余节点。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode*L = NULL, *q = NULL;
	if (l1 == NULL&&l2 == NULL)
		return NULL;
	if (l1 == NULL&&l2 != NULL)
		return l2;
	if (l1 != NULL&&l2 == NULL)
		return l1;
	if (l1->val <= l2->val)//选取较小的头结点为返回的链表头结点；
	{
		L = l1;
		l1 = l1->next;
	}
	else
	{
		L = l2;
		l2 = l2->next;
	}
	q = L;
	while (l1 != NULL&&l2 != NULL)//依次比较；
	{
		if (l1->val <= l2->val)
		{

			q->next = l1;
			l1 = l1->next;
		}
		else
		{
			q->next = l2;
			l2 = l2->next;
		}
		q = q->next;
	}
	if (l1 != NULL)//当其中一个链表比较完后直接将剩余的链表插入到返回链表的为指针后面；
		q->next = l1;
	if (l2 != NULL)
		q->next = l2;
	return L;
    }
};

本文出自 “算法设计” 博客，请务必保留此出处http://shineprince.blog.51cto.com/10293320/1913912

Merge Two Sorted Lists