Leetcode–Merge Two Sorted Lists

The Problem:

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Notes:

  1. This is a basic question, just pay attention to the head and null.

Java Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode fkHead = new ListNode(0);
        ListNode pre = fkHead;
        while(l1!=null && l2 != null){
            if(l1.val < l2.val){
                pre.next = l1;
                l1 = l1.next;
            }
            else{
                pre.next = l2;
                l2 = l2.next;
            }
            pre = pre.next;
        }
        if(l1!= null){
            pre.next = l1;
        }
        if(l2!= null){
            pre.next = l2;
        }
        return fkHead.next;
    }
}

Leetcode–Merge k Sorted Lists

The Problem:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Notes:

  1. First straightforward solution: just like doing merge two sorted list. Examine head node of each list, add the min one to result, complexity is O(k*k*n), k is number of lists, n is number of element in each list.
  2. A better solution is to maintain a priority queue of k candidates from each list, each iteration update the queue and get the min number, no need to traverse k numbers again to get min, complexity is O(k*n).

Java Solution I

/**
 * 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(List<ListNode> lists) {
        int k = lists.size();
        if(k==0) return null;
        ListNode[] pointers = new ListNode[k];
        for(int i = 0; i < k; i++){
            pointers[i] = lists.get(i);
        }
        ListNode fkHead = new ListNode(0);
        ListNode pre = fkHead;
        while(true){
            int min = Integer.MAX_VALUE;
            int useindex = -1;
            for(int i = 0; i < k; i++){
                if(pointers[i] != null && pointers[i].val < min){
                    min = pointers[i].val;
                    useindex = i;
                }
            }
            if(useindex==-1)
                break;
            pre.next = pointers[useindex];
            pre = pre.next;
            pointers[useindex] = pointers[useindex].next;
        }
        pre.next = null;
        return fkHead.next;
    }
}

Java Solution II

/**
 * 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(List<ListNode> lists) {
        int k = lists.size();
        if(k==0) return null;
        PriorityQueue<ListNode> queue = new PriorityQueue(k, new NodeComp());

        for(int i = 0; i < k; i++){
            if(lists.get(i)!= null){
                queue.add(lists.get(i));   
            }
        }
        ListNode fkHead = new ListNode(0);
        ListNode pre = fkHead;
        while(true){
            if(queue.size()==0)
                break;
            ListNode min = queue.poll();
            pre.next = min;
            pre = pre.next;
            if(min.next != null)
                queue.add(min.next);
        }
        pre.next = null;
        return fkHead.next;
    }
    
    
}
class NodeComp implements Comparator<ListNode>{
    public int compare(ListNode a, ListNode b){
        return a.val-b.val;
    }
}

Leetcode–Merge Intervals

The Problem:

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Notes:

  1. First needs to sort the list by the start of intervals, use Java collections.sort, but need to implement a comparator.
  2. While iterating the list, record the previous one, if found overlap, update the previous one with merged end, then delete the current one.

Java Solution

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if(intervals.size()==0) return intervals;
        Collections.sort(intervals, new Comp());
        
        ListIterator<Interval> iterator = intervals.listIterator();
        Interval pre = iterator.next();
        while(iterator.hasNext()){
            Interval cur = iterator.next();
            if(cur.start > pre.end){
                pre = cur;
                continue;
            }
            else{
                pre.end = Math.max(pre.end, cur.end);
                iterator.remove();
            }
        }
        return intervals;
    }
}

class Comp implements Comparator<Interval>{
    public int compare(Interval a, Interval b){
        return a.start-b.start;
    }
}

Leetcode–Insert Interval

The Problem:

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Notes:

  1. The original list is valid, so we can take advantage of that, when traversing the list, if the new interval overlap with any in the original list, remove the one in the list, and update the new interval to the merge of those two.
  2. Use iterator to operate (add/remove) on the list at the same time of traversing. Note that when doing add(), should go to previous first, because when get to know the location of add, in fact we need add in front of current.
  3. To make the code concise and easy to read : For the condition to find overlapping can be very messy to list 4 overlapping ways, instead find those no-overlapping case first, and all overlapping case will be in else, then the merge can be done using Math.min/max instead of consider each case individually.

Java Solution

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if(intervals.size()==0 ){
            intervals.add(newInterval);
            return intervals;
        }
        
        ListIterator<Interval> iterator = intervals.listIterator();
        boolean added = false;
        while(iterator.hasNext()){
            Interval  iter= iterator.next();
            
            if(iter.end < newInterval.start){
                continue;
            }
            else if (iter.start > newInterval.end){
                iterator.previous();
                iterator.add(newInterval);
                return intervals;
            }
            else{
                newInterval.start = Math.min(newInterval.start, iter.start);
                newInterval.end = Math.max(newInterval.end, iter.end);
                iterator.remove();
            }

        }
        intervals.add(newInterval);
        return intervals;
    }
}

Leetcode–Convert Sorted Array to Binary Search Tree

The Problem:

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Notes:

  1. BST is left node left less than parent then less than right. As the input array is in ascending order, in each recursion , take the middle element as parent,  first half start a branch to construct left child, latter half start another branch to construct right child.

Java Solution

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        int len = num.length;
        if(len==0) return null;
        return constructTree(num, 0, len-1);
        
    }
    
    private TreeNode constructTree(int[] num, int start, int end){
        if(start > end) return null;
        int mid = (start+end)/2;
        TreeNode parent = new TreeNode(num[mid]);
        parent.left = constructTree(num, start, mid-1);
        parent.right = constructTree(num, mid+1, end);
        return parent;
    }
}