合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围:节点总数 ,每个节点的val满足
要求:时间复杂度
public ListNode mergeKLists (ArrayList<ListNode> lists) { // write code here if (lists == null || lists.isEmpty()) return null; Iterator<ListNode> it = lists.iterator(); ListNode res = it.next(); while (it.hasNext()) res = merge(res, it.next()); return res; } private ListNode merge(ListNode a, ListNode b) { if (a == null) return b; if (b == null) return a; if(a.val <= b.val) { a.next = merge(a.next, b); return a; } else { b.next = merge(b.next, a); return b; } }
多链表合并 import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param lists ListNode类ArrayList * @return ListNode类 */ public ListNode mergeKLists (ArrayList<ListNode> lists) { // write code here ListNode head=new ListNode(0), cur=head, min=head; int minIdx=0; while(true){ min=null; for(int i=0;i<lists.size();++i){ if(lists.get(i)!=null){ if(min==null){ min=lists.get(i); minIdx=i; }else if(min.val>lists.get(i).val){ min=lists.get(i); minIdx=i; } } } if(min==null) break; cur.next=min; cur=min; lists.set(minIdx, min.next); } return head.next; } }
public ListNode mergeKLists(ArrayList<ListNode> lists) { PriorityQueue<ListNode> list = new PriorityQueue<>(new Comparator<ListNode>() { @Override public int compare(ListNode o1, ListNode o2) { if (o1.val < o2.val) { return -1; } else if (o1.val > o2.val) { return 1; } else { return 0; } } }); // write code here ListNode result = null; //把所有node放到优先级队列中,自动排序,最后一个node的next设置为null即可 for (ListNode listNode : lists) { if (null == listNode) { continue; } while (null != listNode) { list.add(listNode); listNode = listNode.next; } } ListNode cur = null; while (!list.isEmpty()) { if (null == result) { result = cur = list.poll(); } else { cur.next = list.poll(); cur = cur.next; } } if (null != cur) { cur.next = null; } return result; }
public ListNode mergeKLists (ArrayList<ListNode> lists) { PriorityQueue<ListNode> pq = new PriorityQueue<>((x1, x2) -> x1.val - x2.val); // pq.addAll(lists.stream().filter(x -> x != null).toList()); for (ListNode head : lists) { if (head != null) { pq.add(head); } } ListNode dummy = new ListNode(0); ListNode p = dummy; while (pq.size() > 0) { ListNode top = pq.poll(); p.next = top; top = top.next; p = p.next; if (top != null) { pq.add(top); } } return dummy.next; }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param lists ListNode类ArrayList * @return ListNode类 */ public ListNode mergeKLists (ArrayList<ListNode> lists) { // write code here if(lists.size()==0||lists == null) return null; ListNode head = lists.get(0); for(int i = 1;i<lists.size();i++) { head = getNode(head,lists.get(i)); } return head; } public ListNode getNode(ListNode pHead1,ListNode pHead2) { if(pHead1==null) return pHead2; if(pHead2==null) return pHead1; ListNode sentinel = new ListNode(-1); ListNode cur = sentinel; while(pHead1!=null&&pHead2!=null) { if(pHead1.val > pHead2.val) { cur.next = pHead2; pHead2 = pHead2.next; }else{ cur.next = pHead1; pHead1 = pHead1.next; } cur = cur.next; } if(pHead1==null) cur.next = pHead2; else cur.next = pHead1; return sentinel.next; } }
public ListNode mergeKLists (ArrayList<ListNode> lists) { ArrayList<Integer> arr = new ArrayList<>(); ListNode ret = new ListNode(); ListNode temp; for (ListNode listNode : lists) { temp = listNode; while (temp != null) { arr.add(temp.val); temp = temp.next; } } arr.sort(Integer::compareTo); temp = ret; for (int i = 0; i < arr.size(); i++) { temp.val = arr.get(i); if (temp.next == null && i != arr.size() - 1) { temp.next = new ListNode(); temp = temp.next; } } if(ret.val==0&&ret.next==null){ return null; } return ret; } }
public class Solution { public ListNode mergeKLists (ArrayList<ListNode> lists) { // write code here return mergeKList(lists, 0, lists.size() - 1); } // 2、递归+分治 O(logn * n) public ListNode mergeKList(ArrayList<ListNode> lists, int left,int right){ // 递归终点 if(left == right){ return lists.get(left); } if(left > right){ return null; } // 取中间值 int mid = left + ((right - left) >> 1); // 递归调用到最基础的俩俩合并 // 分治左右,实现list中的节点元素可以呈树形俩俩合并,实现logn,配合俩俩合并,总时间复杂度nlogn return merge(mergeKList(lists,left,mid),mergeKList(lists,mid+1,right)); } // 1、(基础)俩个链表合并 O(n) public ListNode merge(ListNode l1, ListNode l2){ if(l1 == null || l2 == null){ return l1 == null ? l2 : l1; } // 返回节点 ListNode dummy = new ListNode(-1); // 操作节点 ListNode cur = dummy; while(l1 != null && l2 != null){ if(l1.val < l2.val){ cur.next = l1; l1 = l1.next; }else{ cur.next = l2; l2 = l2.next; } cur = cur.next; } // 补齐剩下未合并完的链 cur.next = (l1 == null ? l2 : l1); return dummy.next; } }
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param lists ListNode类ArrayList * @return ListNode类 */ public ListNode mergeKLists (ArrayList<ListNode> lists) { // write code here PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator()); for(ListNode list : lists) { while(list != null) { heap.add(list); list = list.next; } } ListNode head = heap.poll(); ListNode tail = head; while(!heap.isEmpty()) { ListNode cur = heap.poll(); tail.next = cur; tail = cur; if(heap.isEmpty()) { tail.next = null; } } return head; } class ListNodeComparator implements Comparator<ListNode> { @Override public int compare(ListNode o1,ListNode o2) { return o1.val - o2.val; } } }
import java.util.*; /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { if (lists.isEmpty()) { return null; } int size = lists.size(); int mod = size%2; ArrayList<ListNode> newList = new ArrayList<>(); if (mod != 0) { newList.add(lists.get(size/2)); } for (int i = 0; i < size/2; i++) { newList.add(merge(lists.get(i), lists.get(size - (i+1)))); } if (1 == newList.size()) { return newList.get(0); } return mergeKLists(newList); } public ListNode merge(ListNode list1, ListNode list2) { if (null == list1) { return list2; } if (null == list2) { return list1; } if (list1.val >= list2.val) { list2.next = merge(list1, list2.next); return list2; } else { list1.next = merge(list1.next, list2); return list1; } } }
public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { ListNode root = null; for(int i=0; i<lists.size(); i++){ if(lists.get(i)==null) { lists.remove(i); i--; } } if(lists.size()==0) return root; int min = lists.get(0).val; int indexMin = 0; for(int i=0; i<lists.size(); i++){ if(min>lists.get(i).val){ indexMin = i; min = lists.get(i).val; } } root= lists.get(indexMin); lists.set(indexMin, lists.get(indexMin).next); root.next = mergeKLists(lists); return root; } }
public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { if (lists == null || lists.size() == 0 ) { return null; } if (lists.size() == 1) { return lists.get(0); } ListNode left = mergeKLists(new ArrayList(lists.subList(0, lists.size() / 2))); ListNode right = mergeKLists(new ArrayList(lists.subList(lists.size() / 2, lists.size()))); ListNode res = new ListNode(-1); ListNode h = res; while (left != null && right != null) { if (left.val < right.val) { h.next = left; left = left.next; } else { h.next = right; right = right.next; } h = h.next; } if (left != null) { h.next = left; } if (right != null) { h.next = right; } return res.next; } }
public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { List<Integer> arr = new ArrayList<>(); for (int i = 0; i < lists.size(); i++) { ListNode inList = lists.get(i); while (inList != null) { arr.add(inList.val); inList = inList.next; } } Object[] aa = arr.toArray(); Arrays.sort(aa); ListNode result = new ListNode(1); ListNode buff = result; System.out.print(aa); for(int i = 0;i<arr.size();i++){ ListNode inResult = new ListNode((int)aa[i]); result.next = inResult; result = result.next; } result.next = null; return buff.next; } }