合并两个有序链表
题目描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路： 首先建立一个头节点方便后续操作，然后开始循环将两个链表的节点值进行比较，如果list1节点的值较小就将该节点尾插至头节点，并且指向list1的指针向后走一位，指向list2的指针不变。如果list2节点值较小，就将list2节点尾插，指向list2指针向后走一位，指向list1指针不变。之后继续循环即可。循环跳出时可能list1或list2并未处理完，这时直接将list1或list2拼接到头节点指向的链表的尾部即可。最终返回头节点的下一个节点的指针即可返回链表。
代码：
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode head=new ListNode(-1);
ListNode ret=head;
ListNode l1=list1,l2=list2;
while(l1!=null&&l2!=null) {
if(l1.val<l2.val) {
head.next=l1;
l1=l1.next;
head=head.next;
} else {
head.next=l2;
l2=l2.next;
head=head.next;
}
}
if(l1!=null) {
head.next=l1;
}
if(l2!=null) {
head.next=l2;
}
return ret.next;
}
}
合并k个升序链表
题目描述：
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
思路： 在已经有合并两个有序链表的知识的基础上，这题并不困难，采用一个循环遍历链表数组，对数组中每个链表按顺序两两合并即可。
代码：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists==null||lists.length==0) {
return null;
}
ListNode ret = lists[0];
for (int i = 1; i < lists.length; i++) {
ret=mergeTwoLists(ret,lists[i]);
}
return ret;
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(-1);
ListNode cur=head;
ListNode p1 = l1, p2 = l2;
while (p1 != null && p2 != null) {
if (p1.val <= p2.val) {
cur.next = p1;
cur = p1;
p1 = p1.next;
} else {
cur.next = p2;
cur = p2;
p2 = p2.next;
}
}
if (p1!=null) {
cur.next=p1;
}
if (p2!=null) {
cur.next=p2;
}
return head.next;
}
}
