Merge k Sorted Lists

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

Approach 1 : Mergesort

If we know how to merge two sorted linked list into one, we can use that as a subroutine to solve this problem:
Merge lists 2 by 2.
E.g. Give 4 lists, l1, l2, l3, l4,

• merge l1 and l4 to l1
• merge l2 and l3 to l2
• merge l1 and l2 to l1

E.g. Give 5 lists, l1, l2, l3, l4, l5,

• merge l1 and l5 to l1
• merge l2 and l4 to l2
• merge l1 and l3 to l1
• merge l1 and l2 to l1

Code:

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int n = lists.size();
        if (n==0) return NULL;
        if (n==1) return lists[0];
        ListNode *r=NULL;
//Pay attention to the following, this makes the total running time O(nlogk), where n is the total number of nodes.
/*each original list has been touched O(logk) times, where k is the number of lists. That said, each node has been touched O(logk) times.
Note that, for odd number of lists, as shown above, some list(s) may be touched more than logk times, but still O(logk) times.*/
        int a=0, b=n-1;
        while(b>0)
        {
            a=0;
            while(a<b)
          lists[a] = merge2Lists(lists[a++],lists[b--]);
        }
        return lists[0];
    }
private:
   ListNode *merge2Lists(ListNode *a, ListNode *b)
   {
       if (a==NULL&&b==NULL) return NULL;
      
       ListNode *r=NULL, *prev=NULL;
       if (a==NULL&&b!=NULL) return b;
       if (a!=NULL&&b==NULL) return a;
       ListNode dummy(-1);
       dummy.next = a->val>b->val?b:a;
       prev = dummy.next;
       if (dummy.next==a)
          a= a->next;
          else
          b=b->next;
      
       while(a!=NULL&&b!=NULL)
       {
           if (a->val<b->val)
           {
               prev->next = a;
               prev = a;
               a=a->next;
           }
           else
              {
                  prev->next=b;
                  prev = b;
                  b=b->next;
              }
       }
       prev->next = a!=NULL?a:b;
       return dummy.next;
   }
};

Approach 2 : HeapSort

Another way to solve the problem is to use heapsort.

 

For k lists, we need to compare k head nodes to find the smallest one. Since we need sort numbers dynamically, heapsort becomes a perfect fit.

• Build up a min heap of the k head nodes of given lists.
• Take the smallest one (i.e. the head of min heap) and add its next to heap.
• Repeat until all nodes in lists have been merged into one list.

Note:

• Since ListNode doesn't have its compare method, we need to provide our own comparator and pass it in during construction time.
   
• If we can build up the priority queue over the given linked list, it can reduce the space complexity from O(k) to O(1).

Code:
class Solution {
public:
class Compare
{
public:
  bool operator() (const ListNode * lhs, const ListNode *rhs) const
  {
    return (lhs->val>rhs->val);
  }
};
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int n=lists.size();
        if (n==0) return NULL;
        if (n==1) return lists[0];
        priority_queue<ListNode *,vector<ListNode*>, Compare> pq;
       
        for (int i=0; i<n; i++)
        {
            if (lists[i]!=NULL)
            pq.push(lists[i]);
        }
       
        ListNode *head=NULL, *cur=NULL;
       
        while(!pq.empty())
        {
            if (head==NULL)
            {
                head = pq.top();
                cur = head;
                pq.pop();
            }
            else
            {
            cur->next = pq.top();
            pq.pop();
            cur = cur->next;
            }
           
            if (cur->next!=NULL)
            pq.push(cur->next);
        }
       
        return head;       
    }
};

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Method:

Use a recursive method which traverse the binary tree. it also returns the max possible sum of left branch and right branch separately. For example, for node A, when it's left and right node recursive call returned, we will know the max possible sum of left branch, right branch.

Compare the sequence sum and record the max history. For node A, check whether left branch + this node + right branch is the maximum, check whether left branch + this node is max， check whether right branch + this node is max.

When recursive method return, we should only return the max sum of one path - either the left branch + this node, or the right branch + this node. So that this is still a single path and can be used to link by node A's parent node.

class Solution {
public:
    int maxPathSum(TreeNode *root) {
       maxSum = INT_MIN;
       dfs(root);
       return maxSum;
    }
   
private:
    int maxSum;
    int dfs(TreeNode *root){
        if (root==NULL) return 0;
        int l = dfs(root->left);
        int r = dfs(root->right);
       
        int sum = root->val;
        if (l>0) sum+=l;
        if (r>0) sum+=r;
       
        maxSum = max(maxSum,sum);
        return max(l,r)>0?max(l,r)+root->val:root->val;
    }
};

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

class Solution {
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int>> ret;
        vector<int> vr;
        helper(root, sum, vr, ret);
       
        return ret;
    }
   
    void helper(TreeNode *root, int sum,vector<int> &vr, vector<vector<int>> &r)
    {
        if (root==NULL)
        return;
        vr.push_back(root->val);
        if (root->val==sum && root->left==NULL && root->right==NULL)
        {
            r.push_back(vr);
        }
       
        helper(root->left, sum-root->val, vr, r);
        helper(root->right, sum-root->val, vr, r);
        vr.pop_back(); //Be very careful about this ,otherwise, there will be TLE
    }
};