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

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

Insertion Sort List

Sort a linked list using insertion sort.

Problem link

Solution

  • insertion sort: the sub-array on the left are sorted, new elements are inserted into the proper position on the left
  • need to search from head every time for the new node to find a place to insert
  • quite complicated, runs slower and painful to debug…
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode *p1 = NULL, *cur, *ret = head, *next, *p2=NULL;
        while (head){
            cur = ret;
            while (cur!=head && cur->val <= head->val){
                p1 = cur;
                cur = cur->next;
            }
            if (cur!=ret){
                if (cur!=head){ // p1->val < head->val < cur->val
                    // insert between p1 and cur
                    next = head->next;
                    p1->next = head;
                    head->next  = cur;
                    head = next;
                    if (p2){
                        p2->next = next;
                    }
                }else{
                    p2 = head;
                    head = head->next;
                }
            }else{ // insert before ret/cur, head node replaces the old head
                if (cur->val > head->val){
                    next = head->next;
                    head->next = cur;
                    ret = head;
                    head = next;
                    if (p2){
                        p2->next = next;
                    }
                }else{ // no need to delete/insert node
                    p2 = head;
                    head = head->next;
                }
            }
        }
        return ret;
    }
};

Dummy head ndoe solution

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode* dummy = new ListNode(INT_MIN);
        dummy->next = head;
        ListNode* left;
        ListNode* tmp;
        head = dummy;
        while (head && head->next){ // evaluting next node to avoid storing the pre pointer
            left = dummy;
            while (head->next->val > left->next->val){
                left = left->next;
            }
            if (head->next!=left->next){ // insert head right before left
                // first delete head->next
                tmp = head->next;
                head->next = head->next->next;
                // insert head->next between left and left->next
                tmp->next = left->next;
                left->next = tmp;
            }else{
                head = head->next;    
            }
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};
Insertion Sort List

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ mn ≤ length of list.

Problem link

Solution

  • should have written test cases myself
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (m==n || !head) return head;
        int i=1;
        ListNode* pre=NULL, *next=NULL, *last=NULL, *old_head = head;
        while (head){
            if (i==m){ // start position
                last = pre;
            }else if (m<i && i<n){ // in between
                next = head->next;
                head->next = pre;
            }else if (i==n){ // end position
                next = head->next;
                head->next = pre;
                if (last){ // head doesn't change
                    last->next->next = next;
                    last->next = head;
                    return old_head;
                } else { // current node becomes the new head 
                    old_head->next = next;
                    return head;
                }
            }
            pre = head;
            if (m<i && i<=n){
                head = next;
            }else{
                head = head->next;    
            }
            ++i;
        }
        return old_head;
    }
};

Dummy head solution

  • always put the dummy head in front of the linked list
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (m==n) return head;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        // head is right before mth node
        for (int i=0; i<m-1; i++){
            head = head -> next;
        }
        
        // reverse the following n-m+1 nodes
        ListNode* pre = head;
        head = head->next;
        ListNode* cur = head;
        ListNode* next;
        bool init = false;
        while (n>=m){
            for (int i=0; i<n-m; i++){ // move to the end of the list to be reversed
                cur = cur->next;
            }
            if (!init){
                init = true;
                next = cur->next;
            }
            pre->next = cur;
            pre = cur;
            cur = head;
            n--;
        }
        pre->next = next;
        head = dummy->next;
        delete dummy;
        return head;
    }
};

An improved solution

  • don’t need to search from the front of the reverse list each time, just put cur in the front of the previous visited nodes
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (m==n) return head;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        // head is right before mth node
        for (int i=0; i<m-1; i++){
            head = head -> next;
        }
        // reverse the following n-m+1 nodes 
        ListNode* pre = head -> next;
        ListNode* cur = pre -> next;
        for (int i=0; i<n-m; i++){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        head->next->next = cur;
        head->next = pre;
        head = dummy->next;
        delete dummy;
        return head;
    }
};
Reverse Linked List II

Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

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

Problem link

Solution

  • two pointer approach
  • be careful about setting the end of list to NULL
class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        if (!head) return NULL;
        ListNode* less=NULL;
        ListNode* lessh=NULL;
        ListNode* greater=NULL;
        ListNode* greaterh=NULL;
        while (head){
            if (head->val<x){
                if (!less){
                    less = head;
                    lessh = head;
                } 
                else{
                    less->next = head;
                    less = less->next;
                }
            }else{
                if (!greater){
                    greater = head;
                    greaterh = head;
                } 
                else{
                    greater->next = head;
                    greater = greater->next;
                }
            }
            head = head->next;
        }
        if (less){
            if (greater) greater->next= NULL;
            less->next = greaterh;
            return lessh;
        }else{
            return greaterh;
        }
    }
};
Partition List