leetcode Question: Sort List

leetcode Question: Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Analysis:

From the post "Common Sorting Algorithms", we know that the sorting algorithms which have O(n log n) complexity are merge sort and quick sort. So in this problem, we can use merge sort to handle!

Different from array data, this problem requires good understanding of linked list operations, e.g., split, merge.  Before doing this problem, I suggest you first check out the problem "Merge Two Sorted List" and "Linked List Cycle", and also the merge sort algorithm itself. Then the problem becomes pretty straightforward.

Like the merge sort, we can do recursively:
(1) Split the list (slow fast pointers)
(2) sort the first part (merge sort)
(3) sort the second part (merge sort)
(4) merge the two parts (merge two sorted lists)

See the code below for details. In this code, the pointer to the pointer (reference pointer) is used, note that to get the pointer where "ptrRef" points, we can use "*ptrRef".

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    // Merge two sorted list (save as the leetcode Question 54: Merge Two Sorted Lists)
    ListNode* sortedMerge(ListNode* l1, ListNode* l2){
        ListNode* res = new ListNode(0);
        ListNode* current = res;
        while (true){
            if (!l1){
                current->next = l2;
                break;
            }
            if (!l2){
                current->next = l1;
                break;
            }
            if (l1->val < l2->val){
                current->next = l1;
                l1 = l1->next;
            }else{
                current->next = l2;
                l2 = l2->next;
            }
            current = current->next;
        }
        return res->next;
    }

    // Split a list into two parts, using slow/fast pointers
    void split(ListNode* head, ListNode** aRef, ListNode** bRef){
        ListNode* slow;
        ListNode* fast;
        if (head==NULL || head->next==NULL){
            *aRef = head;
            *bRef = NULL;
        }else{
            slow = head;
            fast = head;
            while (fast!=NULL && fast->next!=NULL){
                fast = fast->next->next;
                if (fast==NULL){break;} // this is important
                slow = slow->next;
            }
            *aRef = head;
            *bRef = slow->next;
            slow->next=NULL;
        }
    }

    // MergeSort LinkedList
    void mergeSort(ListNode** headRef){
        ListNode* head = *headRef;
        ListNode* a;
        ListNode* b;
        
        if (head==NULL || head->next==NULL){
            return;
        }
        
        split(head,&a,&b);   //split the list
        
        mergeSort(&a);       //sort the first part
        mergeSort(&b);       //sort the second part    
        
        *headRef = sortedMerge(a,b);    // merge two sorted part
    }

    //main function
    ListNode *sortList(ListNode *head) {
        mergeSort(&head);
        return head;
    }
};

leetcode Questions: Reverse Words in a String

Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

click to show clarification.

Clarification:

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

Analysis:

The clarification is very important, during the interview, one should think of these points without hint, and then implement the algorithm.

By checking the clarifications, the programming is straightforward, here provides a simple version which uses buffer strings:

(1)Loop from start to the end of the string:

          (a) if current char is space and word string is empty, continue.

          (b) if current char is space but word string is NOT empty, which means we meet the end of word, then output the word, reset the word, continue.

          (c) if current char is non-space char, add this char to the word string, continue

(2)Handle the last word:

      (a) if the last word is empty, which means the input is empty, or the input has only spaces, or the last char/chars are spaces.  Then just remove the last space in the output string and return.

      (b) if the last word is not empty, add the last word to the front of the output string, then remove the last space in the output string and return.

    

Code (C++):

class Solution {
public:
    void reverseWords(string &s) {
        string word; //tmp string to store each word
        string res; // result string
        int i=0;
        while (i<s.size()){
            if (char(s[i])==' ' && word.empty()){i++;continue;} //multiple spaces
            if (char(s[i])==' ' && !word.empty()){ //first space after a word
                res = word+" "+ res; //store the word
                word=""; //reset the word
                i++; continue;
            }
            if (char(s[i])!=' '){word=word+char(s[i]);i++; continue;} //non-space chars 
        }
        
        if (!word.empty()){ //last word
            s = word+" "+res;
        }else{
            s = res;
        }
        s = s.substr(0,s.size()-1); //eliminate the last space
    }
};

Code (Python):

class Solution:
    # @param s, a string
    # @return a string
    def reverseWords(self, s):
        res = ""    # result string
        word = ""   # single word string
        for ch in s:
            if (ch!=' '):
                word+=ch
            if (ch==' '):
                if (len(word)!=0):
                    if (res!=""):   # add space between words
                        res = ' ' + res
                    res = word + res
                    word = ""
               
        if (len(word)!=0):  #handle the final word
            if (res!=""):
                res = ' ' + res
            res = word + res
            
        return res
                    
                
                
        

[Re-view] Tree Traversal (PreOrder, InOrder, PostOrder): Recursion and Non-Recursion(Iteration)

[Re-view] Tree Traversal (PreOrder, InOrder, PostOrder):  Recursion and Non-Recursion(Iteration)

Introduction

In this post, I would like to talk one important algorithm---- Tree Traversal. Tree traversal is a basic but crucial concept in data structure and algorithm, which is also very hot in interviews. In this post, I assume that you have already had the idea of "what is binary tree?", "what is tree traversal?", and "what is stack?". I will focus on Recursive and Non-Recursive traversal, for PreOrder, InOrder, PostOrder, and Level Order of binary tree. Algorithm description with GIF animation are provided along with the C++ implementations. The code can be run and tested in leetcode online judge as well.

Actually the "three order" traversal is easily to memorize in this way:  Where is the root? When the root is in the first place to be visited (root->left->right), then it is "pre" order, when the root is in the middle to be visited (left->root->right), then it is "in" order, and when the root is last to be visited, it is "post" order.

PreOrder Traversal:

Description:

PreOrder traversal is according to the root, left and right order traversing the binary tree.

Recursive traversal is straightforward:  we first visit the root node, then traverse its left child, then its right child.

Non-Recursive traversal is to ulitize the data structure stack. There are three steps for this algorithm:

(1) Initialize the stack. Push the root node into stack.

(2) While the stack is not empty do:

        (a) Pop the top node from the stack.

        (b) Store the top node

        (c) Push the top node's right child into stack

        (d) Push the top node's left child into stack

(3) Output the stored sequence.

Animation(non-recursive):

Code (PreOrder Traversal):

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
      // preorder traversal: recursion 
    void pre_recur(TreeNode* root, vector<int> &res){
        if (!root){         //if null node, return
            return;
        }else{
            res.push_back(root->val); // traverse root child
            if (root->left){    
                pre_recur(root->left,res); //traverse left child
            }
            if (root->right){
                pre_recur(root->right,res); //traverse right child
            }
        }
    }
    
    // preorder traversal: non-recursion
    void pre_norecur(TreeNode* root,vector<int> &res){
        stack<TreeNode*> st;
        st.push(root);   //initialize stack
        
        TreeNode* tmp;
        while (!st.empty()){
            tmp=st.top();  //get the top node in stack 
            st.pop();
            res.push_back(tmp->val); //store the root value
            if (tmp->right){st.push(tmp->right);} //push right child into stack 
            if (tmp->left){st.push(tmp->left);} //push left child into stack 
        }
    }
    
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        if (!root){return res;}
        
        //pre_recur(root,res);   //recursive traversal 
        pre_norecur(root,res); //non-recursive traversal
        return res;
    }
};

InOrder Traversal:

Description:

InOrder traversal is according to the left, root, and right order traversing the binary tree.

Recursive traversal is straightforward:  we first traverse the left child, then visit the root node, then traverse the right child.

Non-Recursive traversal is to ulitize the data structure stack. There are three steps for this algorithm:

(1) Initialize the stack. Set root as the current node. Push the current node into stack.

(2) Loop until finished (while true):

        (a) If current has left child:

                (i)Push left child into stack.

                (ii)Current node = current node's left child 

        (b) If current has NO left child:

                (i)If stack is empty: exit

                (ii)If stack is NOT empty:

                      Pop the top node in the stack.

                      Store the top node for output.

                      Set current node = top node's right child.              

(3) Output the stored sequence.

Animation(non-recursive):

Code (InOrder Traversal):

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // inorder traversal: recursion 
    void in_recur(TreeNode* root, vector<int> &res){
        if (!root){         //if null node, return
            return;
        }else{
            if (root->left){in_recur(root->left,res);} //traverse left child
            res.push_back(root->val); // traverse root child
            if (root->right){in_recur(root->right,res);} //traverse right child
        }
    }
    
    // inorder traversal: non-recursion
    void in_norecur(TreeNode* root,vector<int> &res){
        stack<TreeNode*> st;
        while (true){
            if (root){  // keep pushing the left child of current node
                st.push(root);
                root=root->left;
            }else{
                if (!st.empty()){   
                    TreeNode* top = st.top();   //pop the top node in the stack
                    st.pop();
                    res.push_back(top->val);    //output the top node
                    root=top->right;            //set current node=right child of top node
                }else{
                    break;  //if the stack is empty, then exit
                }
            }
        }
    }

    vector<int> inorderTraversal(TreeNode *root) {
       vector<int> res;
        if (!root){return res;}
        //in_recur(root,res);   //recursive traversal 
        in_norecur(root,res); //non-recursive traversal
        return res;
    }
};

PostOrder Traversal:

Description:

PostOrder traversal is according to the left, right, and root order traversing the binary tree.

Recursive traversal is straightforward:  we first traverse the left child, then traverse the right child, then visit the root node.

Non-Recursive traversal is to ulitize the data structure stack. Two stacks is used in this algorithm. Stack 2 is used to store the result. There are three steps:

(1) Initialize the stack. Push the root node into stack.

(2) While the stack is not empty do:

        (a) Pop the top node from the stack 1.

        (b) Push the top node into stack 2.

        (c) Push the top node's left child into stack 1.

        (d) Push the top node's right child into stack 1.

(3) Pop all the nodes in Stack 2 to get the result.

Animation(non-recursive):

Code (PostOrder Traversal):

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // postorder traversal: recursion 
    void post_recur(TreeNode* root, vector<int> &res){
        if (!root){         //if null node, return
            return;
        }else{
            if (root->left){    
                post_recur(root->left,res); //traverse left child
            }
            if (root->right){
                post_recur(root->right,res); //traverse right child
            }
            res.push_back(root->val); // traverse root child
        }
    }
    
    // postorder traversal: non-recursion
    void post_norecur(TreeNode* root,vector<int> &res){
        stack<TreeNode*> st1;
        stack<TreeNode*> st2;
        st1.push(root);   //initialize stack one
        
        TreeNode* tmp;
        while (!st1.empty()){
            tmp=st1.top();  //get the top node in stack 1
            st1.pop();  
            st2.push(tmp);  //push into stack 2
            if (tmp->left){st1.push(tmp->left);} //push left child into stack 1
            if (tmp->right){st1.push(tmp->right);} //push right child into stack 1
        }
        
        while (!st2.empty()){  //output the stack 2
            tmp=st2.top();
            st2.pop();
            res.push_back(tmp->val);
        }
        
    }

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        if (!root){return res;}
        
        //post_recur(root,res);   //recursive traversal 
        post_norecur(root,res); //non-recursive traversal
        return res;
    }
};