一、题目描述
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例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） 只额外申请了一个头结点和一个指针
