目录
一、题目描述
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：
0 <= 链表长度 <= 1000
二、思路讲解
两个指针分别从两个链表的头出发， 哪个节点的值小，就把他加到公共节点的后面。等某一个链表遍历完之后，就把没遍历完的链表直接放到公共链表的后面。
由于题目中并没有给出公共链表的头结点，我们可以随意申请一个节点head，将他作为公共链表的头，操作完成后直接返回head.next即可。
三、Java代码实现
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0); //申请头结点
ListNode p = head; //指针，初始化指向公共链表头结点
//一旦有一个链表为空，跳出
while(l1!=null && l2!=null){
if(l1.val <= l2.val){
//保存l1的后面部分
ListNode next = l1.next;
p.next = l1;
p.next.next = null;
p = p.next;
l1 = next;
} else {
ListNode next = l2.next;
p.next = l2;
p.next.next = null;
p = p.next;
l2 = next;
}
}
//将剩余部分加到公共指针后面
if(l1!=null){
p.next = l1;
}
if(l2!=null){
p.next = l2;
}
return head.next;
}
}四、时空复杂度分析
时间复杂度： O（M+N） 需要遍历两个链表
空间复杂度： O（1） 只额外申请了一个头结点和一个指针
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/125058.html
