Description
Intersection of Two Linked Lists
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.
将两个排序链表合并为一个新的排序链表。
Examples
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
Answer
Compare the smallest value of both least at one time and add the smaller node into the result list. And do not forget about the tails.
Time Complexity
O(n)
Code
C++
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1) return l2;
if(!l2) return l1;
ListNode *head = new ListNode(0);
ListNode *tmp = head;
while(l1 && l2)
{
if(l1->val < l2->val)
{
tmp->next = l1;
l1 = l1->next;
}
else
{
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
}
if(l1) tmp->next = l1;
else tmp->next = l2;
return head->next;
}
};
