将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的，且合并后新链表依然有序。
数据范围：链表长度 
，链表中的值 
要求：空间复杂度 %5C)
,时间复杂度 %20%5C)
[编程题]合并有序链表
解法1 递归思路
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode mergeNode = null;
if (l1.val < l2.val) {
mergeNode = l1;
mergeNode.next = mergeTwoLists(l1.next, l2);
} else {
mergeNode = l2;
mergeNode.next = mergeTwoLists(l1, l2.next);
}
return mergeNode;
}
} 解法2 循环思路
public class Solution {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
cur = cur.next;
l1 = l1.next;
} else {
cur.next = l2;
cur = cur.next;
l2 = l2.next;
}
}
if (l1 != null) {
cur.next = l1;
}
if (l2 != null) {
cur.next = l2;
}
return dummy.next;
}
发表于 2019-11-04 10:59:25
回复(5)
/**Java
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/*
思路：
1.输入问题：考虑为空！
2.新链表的第一个结点问题，由于一般情况下第一个结点都需要特殊处理，比较实用的解决办法是在第一个结点前增加一个虚拟的头结点(例如下面的head)，讲实际的第一个结点一般化。最后输出的时候输出这个虚拟结点的下一个结点就OK
3.如何为新链表选择下一个结点（已经虚拟出第一个结点了。）这个比较容易，比大小就OK了。取小的并并在此链表前进一步。
4.注意循环的终止条件！
5.终止后并没有结束！
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head= new ListNode(0);//问题2
ListNode p = head;
while(l1!=null&&l2!=null){//问题3和4
if(l1.val<=l2.val){
p.next=l1;
l1=l1.next;
}else{
p.next=l2;
l2= l2.next;
}
p=p.next;
}
if(l1!=null){//问题1和5
p.next=l1;
}
if(l2!=null){
p.next=l2;
}
return head.next;
}}
发表于 2015-08-14 21:45:03
回复(10)
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode cur = head;
while (l1 != null && l2 != null) {
if(l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 == null) ? l2 : l1;
return head.next;
}
}
发表于 2016-11-05 17:09:12
回复(3)
**题目描述：**
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.
把两个有序链表合并成一个链表，新的链表也是有序的。返回新链表的表头指针。
**题目分析：**
每次选择剩下的节点中最小的，而最小的一定是链表1或者链表2剩下部分的第一个。
用递归大法~
**AC代码：**
```
/**
* 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(l1==NULL)//如果链表1已经空了，直接返回链表2，反之同理
return l2;
if(l2==NULL)
return l1;
ListNode *Head;
if(l1->val<=l2->val)//找较小的节点
{
Head=l1;
Head->next=mergeTwoLists(l1->next,l2);
}
else
{
Head=l2;
Head->next=mergeTwoLists(l1,l2->next);
}
return Head;
}
}; ```
发表于 2019-06-11 17:06:21
回复(0)
这道题说起来还蛮简单的
总体的思想就是归并排序合并的思想，包括 l1 l2 已经有序所以只需要有序比对合并即可。
注意边界条件及一些临时指针即可
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param l1 ListNode类
* @param l2 ListNode类
* @return ListNode类
*/
public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
// write code here
if(l1==null&&l2==null){
return null;
}
if(l1!=null&&l2==null){
return l1;
}
if(l1==null&&l2!=null){
return l2;
}
//初始化新链表头节点 这里注意 l1 l2 为有序 类似归并排序
ListNode resultNodeHead=null;
if(l1.val<l2.val){
resultNodeHead=l1;
l1=l1.next;
}else{
resultNodeHead=l2;
l2=l2.next;
}
ListNode tmpNode=resultNodeHead;
while(l1!=null&&l2!=null){
if(l1.val<l2.val){
tmpNode.next=l1;
l1=l1.next;
}else{
tmpNode.next=l2;
l2=l2.next;
}
tmpNode=tmpNode.next;
}
while(l1!=null){
tmpNode.next=l1;
l1=l1.next;
tmpNode=tmpNode.next;
}
while(l2!=null){
tmpNode.next=l2;
l2=l2.next;
tmpNode=tmpNode.next;
}
return resultNodeHead;
}
}
思考了一下 最后两个 while 没什么必要了，因为是有序链表所以直接指向就可以了
if(l1!=null){
tmpNode.next=l1;
}
if(l2!=null){
tmpNode.next=l2;
}
编辑于 2020-11-28 12:01:58
回复(0)
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
// l1 或者 l2 为空
if(!l1 || !l2) {
return l1 && !l2 ? l1 : l2;
}
ListNode *result = new ListNode(0);
ListNode *head = result;
while(l1 && l2){
if(l1->val < l2->val){
head = head->next = l1;
l1 = l1->next;
}else{
head = head->next = l2;
l2 = l2->next;
}
}
// l2 或者 l2有一个不为空
if(l1 || l2) {
l1 ? (head->next=l1) : (head->next=l2);
}
return result->next;
}
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
// l1 或者 l2 为空
if(!l1 || !l2) {
return l1 && !l2 ? l1 : l2;
}
ListNode *result = new ListNode(0);
ListNode *head = result;
while(l1 && l2){
if(l1->val < l2->val){
head = head->next = l1;
l1 = l1->next;
}else{
head = head->next = l2;
l2 = l2->next;
}
}
// l2 或者 l2有一个不为空
if(l1 || l2) {
l1 ? (head->next=l1) : (head->next=l2);
}
return result->next;
}
};
发表于 2018-06-14 10:17:44
回复(0)
public class Solution {
/**
*
* @param l1 ListNode类
* @param l2 ListNode类
* @return ListNode类
*/
public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val > l2.val) {
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}else{
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}
}
}
发表于 2021-07-31 19:56:21
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param l1 ListNode类
* @param l2 ListNode类
* @return ListNode类
*/
public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
// write code here
if(l1==null&&l2==null){
return null;
}
if(l1==null){
return l2;
}
if(l2==null){
return l1;
}
ListNode list = new ListNode(0);;
ListNode p = list;
while(l1!=null&&l2!=null){
if(l1.val<=l2.val){
p.next = l1;
l1 = l1.next;
p = p.next;
}
else{
p.next = l2;
l2 = l2.next;
p = p.next;
}
}
//方式一
while(l1!=null){
p.next = l1;
p = p.next;
l1 = l1.next;
}
while(l2!=null){
p.next = l2;
p = p.next;
l2 = l2.next;
}
//方式二
if(l1!=null){
p.next = l1;
}
if(l2!=null){
p.next = l2;
}
return list.next;
}
}
编辑于 2021-06-30 17:05:14
回复(0)
public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
// write code here
ListNode head = new ListNode(0);
ListNode s = head;
while(l1 != null && l2 != null){
if(l1.val<l2.val){
s.next = l1;
s = l1;
l1 = l1.next;
}
else{
s.next = l2;
s = l2;
l2 = l2.next;
}
}
if(l1!=null)
s.next = l1;
if(l2!=null)
s.next = l2;
return head.next;
}
发表于 2021-05-30 17:24:45
回复(0)
Python
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # # @param l1 ListNode类 # @param l2 ListNode类 # @return ListNode类 # class Solution: def mergeTwoLists(self , l1 , l2 ): # write code here # 迭代写法 # return self.mergeList(l1,l2) # 递归写法 if l1 == None: return l2 if l2 == None: return l1 if l1.val<=l2.val: l1.next = self.mergeTwoLists(l1.next,l2) return l1 else: l2.next = self.mergeTwoLists(l1,l2.next) return l2 def mergeList(self,l1,l2): if l1 == None: return l2 if l2 == None: return l1 new_l = ListNode(0) head = new_l while l1!=None and l2!=None: if(l1.val<=l2.val): head.next=l1 head = head.next l1=l1.next else: head.next=l2 head = head.next l2=l2.next if(l1==None): head.next=l2 else: head.next=l1 return new_l.next
发表于 2021-04-16 14:35:54
回复(0)
代码没有最长，只有更长：
import java.util.*;
public class Solution {
/**
*
* @param l1 ListNode类
* @param l2 ListNode类
* @return ListNode类
*/
public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
if(l1==null&&l2==null){
return null;
}
if(l1==null&&l2!=null){
return l2;
}
if(l2==null&&l1!=null){
return l1;
}
ListNode node;
ListNode a=l1;
ListNode b =l2;
ListNode head;
if(l1.val<l2.val){
head=l1;
a=a.next;
}else{
head=l2;
b=b.next;
}
node=head;
while(a!=null||b!=null){
if(a!=null&&b!=null){
if(a.val<b.val){
node.next=a;
node=node.next;
a=a.next;
}else{
node.next=b;
node=node.next;
b=b.next;
}
}else if(a!=null){
node.next=a;
node=node.next;
a=a.next;
}else {
node.next=b;
node=node.next;
b=b.next;
}
}
return head;
}
}
发表于 2020-12-09 10:54:42
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param l1 ListNode类
* @param l2 ListNode类
* @return ListNode类
*/
public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode node = head;
while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
node.next = l1;
l1 = l1.next;
}else {
node.next = l2;
l2 = l2.next;
}
node = node.next;
}
if(l1 != null) {
node.next = l1;
}
if(l2 != null) {
node.next = l2;
}
return head.next;
}
}
发表于 2020-11-15 01:05:49
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param l1 ListNode类
* @param l2 ListNode类
* @return ListNode类
*/
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// write code here
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
ListNode *head = new ListNode(0);
ListNode *list = head;
while (!(l1 == NULL || l2 == NULL)) {//循环直到有一个为空
if (l1->val < l2->val) {
list->next = l1;
l1 = l1->next;
} else {
list->next = l2;
l2 = l2->next;
}
list = list->next;
}
if (l2 != NULL) list->next = l2;
if (l1 != NULL) list->next = l1;
return head->next;
}
};
编辑于 2020-11-12 22:45:46
回复(0)
//merge算法 递归版本：把四种情况考虑清楚：l1为空；l2为空；l1当前节点值小于l2；l1当前节点值大于l2；
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null){
return l2;
}
else if(l2 == null){
return l1;
}
else if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
} 迭代版本：
//merge算法 迭代版本：把四种情况考虑清楚：l1为空；l2为空；l1当前节点值小于l2；l1当前节点值大于l2；
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);//这样，建立一个位于-1的node
ListNode prev = prehead;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
prev.next = l1;
l1 = l1.next;
}else{
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
prev.next = l1 == null ? l2 :l1;
return prehead.next;
}
}
编辑于 2020-07-15 20:30:54
回复(0)
/**
* 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(l1==NULL)
return l2;
if(l2==NULL)
return l1;
ListNode *p=new ListNode(-1);
ListNode *q=p;
while(l1!=NULL&&l2!=NULL)
{
if(l1->val<=l2->val)
{
p->next=l1;
p=p->next;
l1=l1->next;
}
else
{
p->next=l2;
p=p->next;
l2=l2->next;
}
}
p->next=l1!=NULL?l1:l2;
return q->next;
}
};
发表于 2020-01-09 19:24:32
回复(2)
/*
* 目的：拼接两个有序链表
* 方法：申请一个头节点，将两个链表中的结点一次加入，最后饭后dummy.next
*/
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode dummy(-1);
ListNode *pre = &dummy;
while(l1&&l2){
if (l1->val<l2->val){
pre->next = l1;
l1= l1->next;
}
else{
pre->next= l2;
l2= l2->next;
}
pre = pre->next;
}
pre->next = l1==nullptr?l2:l1;
return dummy.next;
}
发表于 2019-12-09 17:31:06
回复(0)
//比较两个链表头节点，小者加入新链表，并更新其头节点往后移一个。
//直到某个链表头节点不存在，结束比较，并将另一个链表直接加入新链表。
ListNode* mergeTwoLists(ListNode *l1, ListNode *l2)
{
if (l1 == nullptr)
return l2;
if (l2 == nullptr)
return l1;
//新链表头
ListNode* pHead;
//新链表尾
ListNode* pTail;
if (l1->val < l2->val)
{
pHead = l1;
l1 = l1->next;
}
else
{
pHead = l2;
l2 = l2->next;
}
pTail = pHead;
while (l1 && l2)
{
if (l1->val < l2->val)
{
pTail->next = l1;
pTail = l1;
l1 = l1->next;
}
else
{
pTail->next = l2;
pTail = l2;
l2 = l2->next;
}
}
if (l1)
pTail->next = l1;
if (l2)
pTail->next = l2;
return pHead;
}
发表于 2018-03-14 14:18:10
回复(0)
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
if(l1 == NULL)
return l2;
if(l2 == NULL)
return l1;
ListNode *l3 = new ListNode(0);
ListNode *p3 = l3;
while(l1 && l2)
{
if(l1->val <= l2->val)
{
p3->next = l1;
l1 = l1->next;
}else{
p3->next = l2;
l2 = l2->next;
}
p3 = p3->next;
}
if(l2)
p3->next = l2;
else
p3->next = l1;
return l3->next;
}
};
发表于 2017-07-30 01:14:13
回复(0)
/**
* 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(l1==NULL)
return l2;
if(l2==NULL)
return l1;
ListNode dummy(-1);
ListNode *p=&dummy;
for(;l1!=NULL&&l2!=NULL;p=p->next){
if(l1->val>l2->val){
p->next=l2;
l2=l2->next;
}
else{
p->next=l1;
l1=l1->next;
}
}
p->next=l1!=NULL?l1:l2;
return dummy.next;
}
};
发表于 2017-07-24 10:26:23
回复(0)
这道题的思路前面的大神都已经提出了，我碰到一个问题，我申请了一个指针ListNode* head = new
ListNode(0);之前我没有加(0)，代码是这样的ListNode* head = new
ListNode，编译出错，看到答案里有人的代码是加了(0)，我尝试加了通过了。但是我到vs2015中输入，发现ListNode* head
= new ListNode(0);这个代码会出错，如果ListNode* head = new
ListNode()好像是初始化了head指针，里面的值为0，指针为Null，难道是牛客网的编译器不一样吗？有大神解答吗？谢谢！
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode* head = new ListNode(0);
ListNode* head0;
head0 = head;
while(l1 && l2)
{
if(l1->val< l2->val)
{
head->next = l1;
head = l1;
l1 = l1->next;
}
else
{
head->next = l2;
head = l2;
l2 = l2->next;
}
}
if(l1 == NULL)
{
head->next = l2;
}
else
{
head->next = l1;
}
return head0->next;
ListNode* head = new ListNode(0);
ListNode* head0;
head0 = head;
while(l1 && l2)
{
if(l1->val< l2->val)
{
head->next = l1;
head = l1;
l1 = l1->next;
}
else
{
head->next = l2;
head = l2;
l2 = l2->next;
}
}
if(l1 == NULL)
{
head->next = l2;
}
else
{
head->next = l1;
}
return head0->next;
}
发表于 2017-07-06 22:21:10
回复(0)
问题信息
难度：
195条回答
321收藏
18462浏览
通过挑战的用户
-
2021-09-30 10:59:26
-
2021-09-29 15:55:01 -
2021-09-28 14:46:59 -
2021-09-28 09:33:56
-
2021-09-27 15:23:51
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
