# 21. Merge Two Sorted Lists 合并两个有序链表

• 作者： 负雪明烛
• id： fuxuemingzhu
• 个人博客：http://fuxuemingzhu.cn/open in new window
• 个人公众号：负雪明烛
• 本文关键词：合并，有序链表，递归，迭代，题解，leetcode, 力扣，Python, C++, Java

@TOC

## # 题目描述

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:

``````Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
``````

## # 解题方法

### # 迭代

#### # Python解法

``````# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if not l1: return l2
if not l2: return l1
while l1 and l2:
if l1.val < l2.val:
move.next = l1
l1 = l1.next
else:
move.next = l2
l2 = l2.next
move = move.next
move.next = l1 if l1 else l2
``````

#### # C++解法

C++注意全部是指针操作，要用指针操作符。

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1) cur->next = l1;
else  cur->next = l2;
return dummy->next;
}
};
``````

#### # Java解法

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { liebiaoval = x; }
* }
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
while(l1!=null && l2!=null){
if(l1.val<=l2.val){
move.next=l1;
l1=l1.next;
}else{
move.next=l2;
l2=l2.next;
}
move=move.next;
}
if(l1!=null){
move.next=l1;
}else{
move.next=l2;
}

}
}
``````

AC:1ms

### # 递归

``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if not l1 and not l2:
return None
elif not l1:
return l2
elif not l2:
return l1
if l1.val <= l2.val:
node = l1
node.next = self.mergeTwoLists(l1.next, l2)
else:
node = l2
node.next= self.mergeTwoLists(l1, l2.next)
return node
``````

## # 日期

2016/5/1 19:35:14 2018 年 3 月 11 日 2018 年 11 月 18 日 —— 出去玩了一天，腿都要废了 2019 年 1 月 11 日 —— 小光棍节？