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
题目要求
给定两个有序的链表，把他俩合并成一个有序的链表。
思路
首先明确，这两个链表本身有序，则我们在合并时，一个全部合并完了，另一个直接接到表尾就好了。
创建一个虚拟头结点，指向新表头，即两个head较小的那一个，之后再逐个比较，以此链接下去
代码
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1==null&&l2!=null) {
return l2;
}
if (l2==null&&l1!=null) {
return l1;
}
if (l1==null&&l2==null) {
return l1;
}
ListNode q1=l1,q2=l2,headr=new ListNode(0);//定义两个指针用于遍历，一个虚拟头结点指向新表头
if (q1.val<q2.val) {
headr.next=q1;
q1=q1.next;
}else {
headr.next=q2;
q2=q2.next;
}
ListNode qr =headr.next;//qr用于增加新表
while (q1!=null&&q2!=null) {
if (q1.val<q2.val) {
qr.next=q1;
qr=qr.next;
q1=q1.next;
}else {
qr.next=q2;
qr=qr.next;
q2=q2.next;
}
}
if (q1!=null) {//即q2为null（都不为空就还在上面循环里了），所以把q1剩下的连接到新表尾部
qr.next=q1;
}
if (q2!=null) {
qr.next=q2;
}
return headr.next;//返回新表头
}
