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.
思路一:单刀直入
代码如下：
/** * 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* head,*curr; if(l1 == NULL) return l2; else if(l2 == NULL) return l1; if(l1->val < l2->val) { head = curr = l1; l1= l1->next; } else { head = curr = l2; l2=l2->next; } while(l1 != NULL && l2 != NULL) { if(l1->val < l2->val) { curr->next= l1; curr = l1; l1= l1->next; } else { curr->next= l2; curr = l2; l2=l2->next; } } if(l1!=NULL) curr->next = l1; if(l2 != NULL) curr->next = l2; return head; } };
思路二：没什么好说的，采用递归方法
代码如下：
/** * 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; } } };
