21. 合并两个有序链表

方法1

创建一个哨兵，然后遍历l1和l2，比较l1和l2中的元素，更小的放入到哨兵的尾部，知道l1或l2中到达末尾。然后将哨兵末尾指向没有到达末尾的l1或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) { ListNode *result=new ListNode(0),*p; p=result; while(l1&&l2){ if(l1->val<l2->val){ p->next=l1; l1=l1->next; }else{ p->next=l2; l2=l2->next; } p=p->next; p->next=nullptr; } if(l1==nullptr){ p->next=l2; }else{ p->next=l1; } result=result->next; return result; } };

执行用时 : 28 ms, 在Merge Two Sorted Lists的C++提交中击败了33.78% 的用户 内存消耗 : 8.8 MB, 在Merge Two Sorted Lists的C++提交中击败了88.87% 的用户

方法2

思路和上面一样，但是在每次插入时通过创建新的节点，将插入之赋予新节点，新节点插入到哨兵的末尾…。 /**

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(l1NULL) return l2; if(l2NULL) return l1;

ListNode *result=new ListNode(NULL),*p; p=result; while(l1!=NULL&&l2!=NULL){ p->next=new ListNode(NULL); p=p->next; if(l1->val<=l2->val){ p->val=l1->val; l1=l1->next; }else if(l1->val>l2->val){ p->val=l2->val; l2=l2->next; } } if(l1==nullptr){ p->next=l2; } if(l2==nullptr) { p->next=l1; } return result->next;

} }; 执行用时 : 8 ms, 在Merge Two Sorted Lists的C++提交中击败了99.85% 的用户 内存消耗 : 9.1 MB, 在Merge Two Sorted Lists的C++提交中击败了74.00% 的用户