Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
/** * 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) { // Start typing your Java solution below // DO NOT write main() function if(lists.size() == 0 ) return null; ListNode p = lists.get(0); ListNode head = new ListNode(0); // make a head poin to null for merging head.next = p; for(int i = 1 ; i < lists.size() ; i++){//start from second list not first merge2List(head, lists.get(i)); } return head.next; } public void merge2List(ListNode head, ListNode q){ ListNode p = head.next; ListNode prev = head; if(p == null){ head.next = q; } while(p!= null & q!=null){ if(p.val < q.val){ if(p.next == null){ p.next = q; break; } else{ prev = p; p = p.next; } } else{ ListNode temp = q.next; prev.next = q; q.next = p; prev = q; q = temp; } } } }
public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { if(lists.size() == 0 ) return null; else if(lists.size() ==1) return lists.get(0); ListNode head = null; head = merge(lists.get(0),lists.get(1)); for(int i = 2 ; i < lists.size() ; i++){ head = merge(head,lists.get(i)); } return head; } public ListNode merge(ListNode l1, ListNode l2){ ListNode fakehead = new ListNode(0); ListNode p = fakehead; while(l1!=null && l2 != null){ if(l1.val < l2.val){ p.next = l1; l1 = l1.next; } else{ p.next = l2; l2 = l2.next; } p = p.next; } if(l1!=null){ p.next = l1; } if(l2!=null){ p.next = l2; } return fakehead.next; } }
public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { if(lists == null || lists.size() == 0) return null; Comparator<ListNode> comparator = new Comparator<ListNode>(){ public int compare(ListNode m, ListNode n){ return m.val - n.val; } }; PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(),comparator); for(int i = 0 ; i < lists.size();i++){ if(lists.get(i)!=null) queue.add(lists.get(i)); } ListNode head = null; ListNode run = head; while(!queue.isEmpty()){ if(head == null){ head = queue.poll(); run = head; } else{ run.next = queue.poll(); run = run.next; } if(run.next != null) queue.add(run.next); } return head; } }
learned: priority queue, sort first node among all listnodes, then add last node in queue, as next loop head