LeetCode-合并有序链表问题

合并两个有序链表

题目描述：

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
在这里插入图片描述
思路： 首先建立一个头节点方便后续操作，然后开始循环将两个链表的节点值进行比较，如果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;}
}