# [LeetCode]21.Merge Two Sorted 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.

#### 【代码】

/*********************************
*   日期：2015-01-06
*   作者：SJF0115
*   题目: 21.Merge Two Sorted Lists
*   来源：https://oj.leetcode.com/problems/merge-two-sorted-lists/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
using namespace std;

struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){}
};

class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *p1 = l1,*p2 = l2,*cur = head;
while(p1 != NULL && p2 != NULL){
// 取两个链表头的较小元素
if(p1->val < p2->val){
cur->next = p1;
p1 = p1->next;
}//if
else{
cur->next = p2;
p2 = p2->next;
}//else
cur = cur->next;
}//while
// 如果链表1没有遍历完
while(p1){
cur->next = p1;
p1 = p1->next;
cur = cur->next;
}//while
// 如果链表2没有遍历完
while(p2){
cur->next = p2;
p2 = p2->next;
cur = cur->next;
}//while
cur->next = NULL;
}
};

int main() {
Solution solution;
int A[] = {1,2,4,7,9};
int B[] = {3,5,8,10,11,12};
// 链表1
for(int i = 1;i < 5;i++){
ListNode *node = new ListNode(A[i]);
p1->next = node;
p1 = node;
}//for
// 链表2
for(int i = 1;i < 6;i++){
ListNode *node = new ListNode(B[i]);
p2->next = node;
p2 = node;
}//for
// 输出
while(p){
cout<<p->val<<" ";
p = p->next;
}//while
cout<<endl;
}


#### 【代码二】

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;
}
}
};

#### 【代码三】

public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
for(ListNode *p = head;l1 != NULL || l2 != NULL;p = p->next){
int val1 = (l1 == NULL) ? INT_MAX : l1->val;
int val2 = (l2 == NULL) ? INT_MAX : l2->val;
if(val1 <= val2){
p->next = l1;
l1 = l1->next;
}//if
else{
p->next = l2;
l2 = l2->next;
}//else
}//for
}
};

|
11月前
|

LeetCode刷题---Two Sum（一）
LeetCode刷题---Two Sum（一）
|
9月前
Leetcode 4. Median of Two Sorted Arrays

21 0
|
9月前
Leetcode Find Minimum in Rotated Sorted Array 题解

33 0
|
11月前
|

|

LeetCode - #2 Add Two Numbers

64 0
|
7天前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III

19 6
|
7天前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构

17 4
|
7天前
|

【Leetcode刷题Python】牛客. 数组中未出现的最小正整数

21 2
|
7天前
|

【Leetcode刷题Python】从列表list中创建一颗二叉树

13 7
|
7天前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈

10 4