(完整C++代码）剑指offer：合并两个有序链表

1.递归
2.迭代

#include<iostream>
using namespace std;
//结构。
struct ListNode
{
	int val;
	ListNode* next;
	ListNode(int x) :val(x), next(NULL) {}
};
class solution {
public:

		ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
		{
			if (!l1) return l2;
			if (!l2) return l1;
			ListNode* res = NULL;
			if (l1->val < l2->val)
			{
				res = l1;
				res->next = mergeTwoLists(l1->next, l2);
			}
			else {
				res = l2;
				res->next = mergeTwoLists(l2->next, l1);
			}
			return res;
		}
};
ListNode* creatList()
{
	ListNode* prehead = new ListNode(-1);
	ListNode* dummy = prehead;
	cout << "输入链表，(通过“-1”终止输入):" << endl;
	while (true)
	{
		int value;
		cin >> value;
		cout << " -> ";
		if (value == -1)
			break;
		ListNode* donecreatList = new ListNode(value);
		dummy->next = donecreatList;
		dummy = dummy->next;
	}
	cout << endl;
	return prehead->next;
}
void printList(ListNode* head)
{
	if (!head)
	{
		return;
	}
	ListNode* forprintList;
	forprintList = head;
	while (forprintList)
	{
		cout << " " << forprintList->val;
		forprintList = forprintList->next;
	}
	cout << endl;
}
int main()
{
	solution solute;
	ListNode* l1= creatList();
	ListNode* l2 = creatList();
	ListNode* RES = NULL;
	cout << "给定链表：" << endl;
	printList(l1);
	printList(l2);
	RES= solute.mergeTwoLists(l1,l2);
	cout << "返回：" << endl;
	printList(RES);
	return 0;
}

迭代法核心代码。（替换上面代码类部分就行）

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        if(!l1) return l2;
        if(!l2) return l1;
        ListNode*head=new ListNode(-1);
        ListNode*temp=head;
        while(l1&&l2)
        {
            if(l1->val<l2->val)
            {
               temp->next=l1;
            l1=l1->next;
            }
            else{
                temp->next=l2;
                l2=l2->next;
            }
            temp=temp->next;
        }
        temp->next=(l1)?l1:l2;
        return head->next;
    }