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.
思路.首先判断是否有空链表，如果有，则直接返回另一个链表，如果没有，则开始比较两个链表的当前节点，返回较小的元素作为前驱，并且指针向后移动一位，再进行比较，如此循环，知道一个链表的next指向NULL，将另一个链表的后序元素进行连接即可。
迭代：
/**
* 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) {
if(l1 == NULL) return l2;
if(l2 == NULL) return l1; if(l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l2->next, l1);
return l2;
}
}
};
循环：
/**
* 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) {
if( l1==NULL ) return l2;
if( l2==NULL ) return l1;
ListNode* head = (l1->val > l2->val)?l2:l1;
ListNode* temp;
while(l1!=NULL && l2!=NULL)
{
while(l1->next!=NULL&&l2!= NULL &&l1->next->val <= l2->val)
{
l1 = l1->next;
}
if(l1 != NULL&&l2 !=NULL &&l1->val <= l2->val)
{
temp = l1->next;
l1->next = l2;
l1 = temp;
}
while(l2->next !=NULL&& l1 !=NULL &&l2->next->val <= l1->val)
{
l2 = l2->next;
}
if(l2 != NULL &&l1 != NULL&&l2->val <= l1->val)
{
temp = l2->next;
l2->next = l1;
l2 = temp;
} }
return head;
}
};