將兩個排序鏈表合并為一個新的排序鏈表
您在真實的面試中是否遇到過這個題？
Yes
樣例
給出 1->3->8->11->15->null吸耿，2->null， 返回 1->2->3->8->11->15->null。
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param ListNode l1 is the head of the linked list
* @param ListNode l2 is the head of the linked list
* @return: ListNode head of linked list
*/
void insert(ListNode *head,ListNode *node){
node->next=NULL;
if(head->next==NULL){
head->next=node;
return ;
}
ListNode * pre=head;
ListNode * p=head->next;
while(p!=NULL){
if(p->val>node->val){
node->next=p;
pre->next=node;
return ;
}
else{
p=p->next;
pre=pre->next;
}
}
pre->next=node;
}
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
// write your code here
ListNode * newhead=new ListNode();
ListNode * p=l1;
ListNode * q=l2;
while(p!=NULL){
ListNode * node =p;
p=p->next;
insert(newhead,node);
}
while(q!=NULL){
ListNode * node=q;
q=q->next;
insert(newhead,node);
}
return newhead->next;
}
};
