Merge k Sorted Lists

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

Problem link

Solution

  • using a priority queue to keep the organize the k current candidates
  • note that the default priority_queue in cpp is max_heap, I need to implement my own comparator function that supports min_heap with pointers as elements
struct compNode {
bool operator()(ListNode *p, ListNode *q) const {
            return p->val>q->val;
        }  
    };

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode*, vector<ListNode*>, compNode> q;
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        ListNode* min_node;
        for (auto n:lists){
            if (n){
                q.push(n);
            }
        }
        while (!q.empty()){
            min_node = q.top();
            q.pop();
            cur -> next = min_node;
            cur = cur->next;
            min_node = min_node->next;
            if (min_node) q.push(min_node);
        }
        cur -> next = NULL;
        cur = dummy->next;
        delete (dummy);
        return cur;
    }
};
Merge k Sorted Lists

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Problem link

Solution

  • the random pointer may point to a node that hasn’t been created yet
  • create the linked list first, and then add random pointers in the second pass using hashtable constant-time lookup
  • need two passes
/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        // two lookups: ori.cur ->(using pointer) ori.rand -> new.rand
        unordered_map<RandomListNode*, RandomListNode*> h;
        RandomListNode* dummy = new RandomListNode(0);
        RandomListNode* cur = head;
        RandomListNode* new_cur = dummy;
        // linking next pointers
        while (cur){
            new_cur->next = new RandomListNode(cur->label);
            h[cur] = new_cur->next;
            cur = cur->next;
            new_cur = new_cur->next;
        }
        new_cur->next = NULL;
        // linking random pointers
        cur = head;
        new_cur = dummy->next;
        while (cur){
            new_cur->random = cur->random? h[cur->random]:NULL;
            new_cur = new_cur->next;
            cur = cur->next;
        }
        new_cur = dummy->next;
        delete(dummy);
        return new_cur;
    }
};
Copy List with Random Pointer

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Problem link

Solution

  • The original head could be removed, therefore introduce dummy head to simplify the program
  • be careful about the case where reading the end and still need to delete elements
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode* dummy = new ListNode(0);
        if (!head) return NULL;
        dummy->next = head;
        ListNode* pre = dummy;
        int same = false;
        while (head->next){
            if (head->val == head->next->val){
                same = true;
            }else{ // not equal for now
                if (same == true){
                    pre->next = head->next; // delete
                    same = false;
                }else{
                    pre = head;
                }
            }
            head = head->next;
        }
        if (same == true){
            pre->next = head->next;
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};
Remove Duplicates from Sorted List II

Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Problem link

Solution

  • calculate from right to left
class Solution {
public:
    string addBinary(string a, string b) {
        if (a.empty()) return b;
        if (b.empty()) return a;
        int m = a.size();
        int n = b.size();
        string c;
        bool carry=false;
        int i,j;
        int sum;
        for (i=m-1, j=n-1; i>=0 && j>=0; --i, --j){
            sum = a[i]-'0' + b[j]-'0' + carry;
            carry = sum/2? true:false;
            c = to_string(sum%2) + c;
        }
        if (j>=0){ // run out of a
            for (; j>=0; --j){
                sum = b[j]-'0' + carry;
                carry = sum/2? true:false;
                c = to_string(sum%2) + c;
            }
        }else if (i>=0){ // run out of b
            for (; i>=0; --i){
                sum = a[i]-'0' + carry;
                carry = sum/2? true:false;
                c = to_string(sum%2) + c;
            }
        }
        if (carry==1){
            c = "1" + c;
        }
        return c;
    }
};
Add Binary

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,31,3,2
3,2,11,2,3
1,1,51,5,1

Problem link

Solution

  • one naive approach is to first sort the array, recursively find all permutations on that array, the permutation right after the input one is what we want. In the worst case, it is O(n!)
  • Time Limit Exceeded, also this solution needs extra space
class Solution {
public:
    void nextPermutation(vector<int> &num) {
        vector<int> v(num.begin(), num.end()); // make a new copy
        sort(v.begin(), v.end());
        vector<bool> u(num.size(), false);
        vector<int> next;
        bool equal = false;
        rec(num, v, u, next, equal);
        if (!equal) num = v;
    }
    
    void rec(vector<int> &num, vector<int> &v, vector<bool> &u, vector<int> &next, bool equal){
        for (int i=0; i<v.size(); i++){
            if (!u[i]){
                next.push_back(v[i]);
                if (next.size() == v.size()){
                    if (equal==false){
                        if (next == num) equal = true;
                    }else{
                        num = next;
                        return;
                    }
                }else{
                    u[i] = true;
                    rec(num, v, u, next, equal);
                    if (next.size() == v.size() && equal){
                        num = next;
                        return;   
                    } 
                    u[i] = false;
                }
                next.pop_back();
            }
        }
    }
};

In-place solution using swapping

  • expanding the right segment when all the elements in the right segment are sorted in decreasing order
  • after expansion, reverse all elements in the right segments
  • be careful about equal elements in the array
class Solution {
public:
    void nextPermutation(vector<int> &num) {
        // find right segment
        int right;
        int n=num.size();
        int i;
        int j;
        for (i=n-1; i>=1 && num[i-1]>=num[i]; --i);
        if (i==0){// start from lowest possible order
            sort(num.begin(), num.end());
            return;
        }
        // i is boundary of the right segment, find next element in right that is greater than num[right-1]
        right = i;
        for (i=n-1; num[right-1]>=num[i]; --i);
        swap(num[right-1], num[i]);
        // reverse right:n-1
        i=right; j=n-1;
        while (i<j){
            swap(num[i],num[j]);
            i++;
            j--;
        }
    }
};
Next Permutation

Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Problem link

Solution

  • dummy head, to avoid checking the head node
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        int i;
        int start = 0;
        ListNode* next;
        ListNode* cur = head->next;
        ListNode* pre;
        while (cur){
            for (i=0; i<k && cur; i++, cur = cur->next); // check whether there are sufficient 
            if (i==k){
                pre = head->next;
                cur = pre->next;
                for (i=0; i<k-1; i++){
                    next = cur->next;
                    cur->next = pre;
                    pre = cur;
                    cur = next;
                }
                head->next->next = cur;
                next = head->next;
                head->next = pre;
                head = next;
                cur = head->next;
            }else{ // reaching the end of list
                head = dummy->next;
                delete dummy;
                return head;
            }
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};
Reverse Nodes in k-Group

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1]. Problem link Solution

  • recursive solution, only when last element is not  (the same and used)
class Solution {
public:
    vector<vector > permuteUnique(vector &num) {
        sort(num.begin(), num.end());
        vector<vector> vv;
        vector v;
        vector u(num.size(), false);
        rec(vv, v, u, num);
        return vv;
    }
    
    void rec(vector<vector> &vv, vector &v, vector &u, vector &num){
        for (int i=0; i<num.size(); ++i){
            if (!u[i] && (i==0 || i>0 && !(num[i]==num[i-1] && !u[i-1]))){
                v.push_back(num[i]);
                u[i] = true;
                if (v.size()==num.size()){
                    vv.push_back(v);
                }else{
                    rec(vv, v, u, num);
                }
                v.pop_back();
                u[i] = false;
            }
        }
    }
};
Permutations II