Merge / Split Linked List
Merge Two Sorted List
just set up a dummy node to allow us to easily return the head of the merged list later. We also maintain a prev pointer, which points to the current node for which we are considering adjusting its next pointer. Then, we do the following until at least one of l1 and l2 points to null: ...if the value at l1 is less than or equal to the value at l2, then we connect l1 to the previous node and increment l1. Otherwise, we do the same, but for l2. Then, regardless of which list we connected, we increment prev to keep it one step behind one of our list heads.
After the loop terminates, at most one of l1 and l2 is non-null. Therefore (because the input lists were in sorted order), if either list is non-null, it contains only elements greater than all of the previously-merged elements. This means that we can simply connect the non-null list to the merged list and return it.
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
}
Merge K Sorted List
what is priority queue? There are three requirements
- insert with priority
- pull highest priority element
- peek with O(1)
And how to use heap to implement it?
Heap is special complete binary tree. For example, max-heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node. The fact that a heap is a complete binary tree allows it to be efficiently represented using a simple array. The property of Heap: for the element in position i, the parent's position is (i - 1)/ 2, the child position is i * 2 + 1, (i * 2) + 2
the following is the code using array to implement the heap.
package priorityheap;
import java.util.Arrays;
/**
* 优先队列类（最大优先队列）
*/
public class PriorityHeap {
// ------------------------------ Instance Variables
private int[] arr;
private int size;
// ------------------------------ Constructors
/**
* 优先队列数组默认大小为64
*/
public PriorityHeap() {
this(64);
}
public PriorityHeap(int initSize) {
if (initSize <= 0) {
initSize = 64;
}
this.arr = new int[initSize];
this.size = 0;
}
// ------------------------------ Public methods
public int max() {
return this.arr[0];
}
public int maxAndRemove() {
int t = max();
this.arr[0] = this.arr[--size];
sink(0, this.arr[0]);
return t;
}
public void add(int data) {
resize(1);
this.arr[size++] = data;
pop(size - 1, data);
}
// ------------------------------ Private methods
/**
* key下沉方法
*/
private void sink(int i, int key) {
while (2 * i <= this.size - 1) {
int child = 2 * i + 1;
if (child < this.size - 1 && this.arr[child] < this.arr[child + 1]) {
child++;
}
if (this.arr[i] >= this.arr[child]) {
break;
}
swap(i, child);
i = child;
}
}
/**
* key上浮方法
*/
private void pop(int i, int key) {
while (i > 0) {
int parent = (i - 1) / 2;
if (this.arr[i] <= this.arr[parent]) {
break;
}
swap(i, parent);
i = parent;
}
}
/**
* 重新调整数组大小
*/
private void resize(int increaseSize) {
if ((this.size + increaseSize) > this.arr.length) {
int newSize = (this.size + increaseSize) > 2 * this.arr.length ? (this.size + increaseSize) : 2 * this.arr.length;
int[] t = this.arr;
this.arr = Arrays.copyOf(t, newSize);
}
}
/**
* Swaps arr[a] with arr[b].
*/
private void swap(int a, int b) {
int t = this.arr[a];
this.arr[a] = this.arr[b];
this.arr[b] = t;
}
}
approach 1: time: O(nlogk), space: O(k)
public ListNode mergeKLists(ListNode[] lists) {
//定义优先队列的比较器
Comparator<ListNode> cmp;
cmp = new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
// TODO Auto-generated method stub
return o1.val-o2.val;
}
};
//建立队列
Queue<ListNode> q = new PriorityQueue<ListNode>(cmp);
for(ListNode l : lists){
if(l!=null){
q.add(l);
}
}
ListNode head = new ListNode(0);
ListNode point = head;
while(!q.isEmpty()){
//出队列
point.next = q.poll();
point = point.next;
//判断当前链表是否为空，不为空就将新元素入队
ListNode next = point.next;
if(next!=null){
q.add(next);
}
}
return head.next;
}
approach 2: time: O(nlogk), space: O(1)
how to solve the problem in O(1) space complexity without priority queue?
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode h = new ListNode(0);
ListNode ans=h;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
h.next = l1;
h = h.next;
l1 = l1.next;
} else {
h.next = l2;
h = h.next;
l2 = l2.next;
}
}
if(l1==null){
h.next=l2;
}
if(l2==null){
h.next=l1;
}
return ans.next;
}
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0){
return null;
}
int interval = 1;
while(interval<lists.length){
for (int i = 0; i + interval< lists.length; i=i+interval*2) {
lists[i]=mergeTwoLists(lists[i],lists[i+interval]);
}
interval*=2;
}
return lists[0];
}