题目介绍
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.
Example:
1 | Input: 1->2->4, 1->3->4 |
2 | Output: 1->1->2->3->4->4 |
解
1 | /** |
2 | * Definition for singly-linked list. |
3 | * struct ListNode { |
4 | * int val; |
5 | * ListNode *next; |
6 | * ListNode(int x) : val(x), next(NULL) {} |
7 | * }; |
8 | */ |
9 | class Solution { |
10 | public: |
11 | ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { |
12 | ListNode first(0); |
13 | ListNode* pre = &first; |
14 | while (l1 != NULL && l2 != NULL) { |
15 | if (l2->val < l1->val) { |
16 | pre->next = l2; |
17 | pre = pre->next; |
18 | l2 = l2->next; |
19 | } else { |
20 | pre->next = l1; |
21 | pre = pre->next; |
22 | l1 = l1->next; |
23 | } |
24 | } |
25 | if (l1 != NULL) { |
26 | pre->next = l1; |
27 | } |
28 | if (l2 != NULL) { |
29 | pre->next = l2; |
30 | } |
31 | return first.next; |
32 | } |
33 | }; |
Runtime: 4 ms
Memory Usage: 8.9 MB
