Little bit about quick sort/ quick select

Quick Sort algorithm

This algorithm is one of the efficient and popular sorting algorithms you may encounter in your programming, it majorly includes two parts:

1) First it applies partition function to divide a array  into two sub-arrays;  
2) Then apply itself recursively on these two sub-arrays separately;

The essence of this algorithm is to implement a partition function, which uses two indices to divide a array into right-left sub-arrays, separated by an arbitrary element from the array called pivot element, all elements in the left sub-array are less than the pivot while all elements in the right sub-arrary are bigger than the pivot. 

[code]

int partition(vector<int> &s, int start, int end)
{
      int pivot = s[end];   // could be any element from s
      int pindex = start;
      for( int i = start; i< end; i++) {
          if (s[i] <= pivot) {
              swap(s[pindex], s[i]);
              pindex ++;
          }
      }
      swap(s[pindex], s[end]); 
      return pindex;
}


void quicksort(vector<int> &s, int start, int end)
{
    if (start >= end) return;
    int pindex = partition(s, start, end);
    quicksort(s, start, pindex - 1);
    quicksort(s, pindex + 1 , end);
}

Quick Select algorithm

With the same partition function, we can implement a quick select algorithm.

For example, find the kth smallest item in the array:

[code]

void quickselect(vector<int> &s, int start, int end, int k)
{
    int pindex = partition(s, start, end);
    if (k < pivot) return quickselect(s, first, pivot-1, k);
    if (k > pivot) return quickselect(s, pivot+1, end, k);
    if (k == pivot) return s[pivot];
}

3-way partitioning 

(Dijkstra 3-way partitioning)

The above partitioning are 2-way partitioning, it partition array into 2 parts (or sub-arrays) as we analyzed. Let's find out if we can partition an array into 3 parts so that:
1) left part: the elements less than pivot;
2) middle part: the elements equal to pivot;
3) right part: the elements bigger than pivot; 

(By the way, this can help to solve Dutch national flag problem)

[code]

void threewaypartitions(vector<int> &s, int start, int end, int ke)
{
    int pivot = ke;
    int lt = start, gt = end;
    int i = lt;
    for(;i<=gt;) {
       if(s[i] < pivot)      swap(s[i++], s[lt++]);
       else if (s[i] > pivot) swap(s[i], s[gt--]);
       else i++;
    }
}

Object Oriented Design Patterns

Understanding design patterns is crucial for software development as they provide proven solutions to common design problems. Below are some fundamental design patterns with code samples in C++.

Singleton Pattern:

The Singleton Pattern ensures a class has only one instance and provides a global point of access to it.

#include<iostream>
#include<memory>

using namespace std;

class Singleton {
public:
    static Singleton* Instance() {
        if (!mInstance)
            mInstance = new Singleton();
        return mInstance;
    }

    void Display() {
        cout << "This is singleton instance" << endl;
    }

    static void Destroy() {
        if (mInstance) {
            delete mInstance;
            mInstance = nullptr;
        }
    }

protected:
    Singleton() {
        cout << "Singleton constructor" << endl;
    }
    ~Singleton() {
        cout << "Singleton destructor" << endl;
    }

private:
    static Singleton* mInstance;
};

Singleton* Singleton::mInstance = nullptr;

int main() {
    Singleton* sgn = Singleton::Instance();
    sgn->Display();
    Singleton::Destroy();
    return 0;
}

Factory Pattern:

The Factory Pattern defines an interface for creating an object but lets subclasses alter the type of objects that will be created.

#include<iostream>

using namespace std;

class Product {
public:
    Product() {};
    virtual ~Product() {};
};

class ConcreteProduct : public Product {
public:
    ConcreteProduct() {
        cout << "Construct of ConcreteProduct" << endl;
    }
    virtual ~ConcreteProduct() {
        cout << "Destruct of ConcreteProduct" << endl;
    }
};

class Factory {
public:
    Factory() {};
    virtual ~Factory() {};
    virtual Product* CreateProduct() = 0;
};

class ConcreteFactory : public Factory {
public:
    ConcreteFactory() {
        cout << "Construct of ConcreteFactory" << endl;
    }
    virtual ~ConcreteFactory() {
        cout << "Destruct of ConcreteFactory" << endl;
    }
    virtual Product* CreateProduct() {
        return new ConcreteProduct();
    }
};

int main() {
    Factory* factory = new ConcreteFactory();
    Product* p = factory->CreateProduct();
    delete p;
    delete factory;
    return 0;
}

Prototype Pattern:

The Prototype Pattern is used to create a new object by copying an existing object, known as the prototype.

#include<iostream>
#include<string>

using namespace std;

class Prototype {
public:
    virtual ~Prototype() {};
    virtual Prototype* Clone() const = 0;

protected:
    Prototype() { cout << "Prototype constructor" << endl; }
};

class ConcretePrototype : public Prototype {
public:
    ConcretePrototype() {};
    ConcretePrototype(const ConcretePrototype& cp) {
        cout << "ConcretePrototype copy ..." << endl;
    }
    Prototype* Clone() const override {
        return new ConcretePrototype(*this);
    }
};

int main() {
    Prototype* p = new ConcretePrototype();
    cout << "Clone is called" << endl;
    Prototype* p1 = p->Clone();
    delete p;
    delete p1;
    return 0;
}

Builder Pattern:

The Builder Pattern separates the construction of a complex object from its representation, allowing the same construction process to create different representations.

#include<string>
#include<iostream>

using namespace std;

class Product {
public:
    Product() {};
    ~Product() {};
    void ProductPart() {};
};

class Builder {
public:
    virtual ~Builder() {};
    virtual void BuildPartA(const string& buildPara) = 0;
    virtual void BuildPartB(const string& buildPara) = 0;
    virtual void BuildPartC(const string& buildPara) = 0;
    virtual Product* GetProduct() = 0;
protected:
    Builder() {};
};

class ConcreteBuilder : public Builder {
public:
    ConcreteBuilder() {};
    ~ConcreteBuilder() {};
    void BuildPartA(const string& buildPara) override {
        cout << "Build Part A ---" << buildPara << endl;
    }
    void BuildPartB(const string& buildPara) override {
        cout << "Build Part B ---" << buildPara << endl;
    }
    void BuildPartC(const string& buildPara) override {
        cout << "Build Part C ---" << buildPara << endl;
    }
    Product* GetProduct() override {
        BuildPartA("pre-defined");
        BuildPartB("pre-defined");
        BuildPartC("pre-defined");
        return new Product();
    }
};

class Director {
public:
    Director(Builder* bld) : mbld(bld) {}
    ~Director() {};
    void Construct() {
        mbld->BuildPartA("user-defined");
        mbld->BuildPartB("user-defined");
        mbld->BuildPartC("user-defined");
    }
private:
    Builder* mbld;
};

int main() {
    Director* d = new Director(new ConcreteBuilder());
    d->Construct();
    delete d;
    return 0;
}

Adapter Pattern:

The Adapter Pattern allows the interface of an existing class to be used as another interface. It is often used to make existing classes work with others without modifying their source code.

#include<iostream>

using namespace std;

class Target {
public:
    virtual void Request() {
        cout << "Target Request" << endl;
    }
    virtual ~Target() {}
};

class Adaptee {
public:
    void SpecificRequest() {
        cout << "Adaptee SpecificRequest" << endl;
    }
};

class Adapter : public Target {
public:
    Adapter(Adaptee* adaptee) : adaptee_(adaptee) {}
    void Request() override {
        adaptee_->SpecificRequest();
    }
private:
    Adaptee* adaptee_;
};

int main() {
    Adaptee* adaptee = new Adaptee();
    Target* target = new Adapter(adaptee);
    target->Request();
    delete target;
    delete adaptee;
    return 0;
}

Composite Pattern:

The Composite Pattern composes objects into tree structures to represent part-whole hierarchies. It allows clients to treat individual objects and compositions of objects uniformly.

#include<iostream>
#include<vector>
#include<string>

using namespace std;

class Component {
public:
    virtual void Operation() = 0;
    virtual void Add(Component* component) {}
    virtual void Remove(Component* component) {}
    virtual Component* GetChild(int index) { return nullptr; }
    virtual ~Component() {}
};

class Leaf : public Component {
public:
    void Operation() override {
        cout << "Leaf Operation" << endl;
    }
};

class Composite : public Component {
public:
    void Operation() override {
        for (auto component : children_) {
            component->Operation();
        }
    }

    void Add(Component* component) override {
        children_.push_back(component);
    }

    void Remove(Component* component) override {
        children_.erase(remove(children_.begin(), children_.end(), component), children_.end());
    }

    Component* GetChild(int index) override {
        if (index < 0 || index >= children_.size()) {
            return nullptr;
        }
        return children_[index];
    }

private:
    vector<Component*> children_;
};

int main() {
    Composite* root = new Composite();
    Leaf* leaf1 = new Leaf();
    Leaf* leaf2 = new Leaf();
    Composite* subtree = new Composite();

    root->Add(leaf1);
    root->Add(subtree);
    subtree->Add(leaf2);

    root->Operation();

    delete root;
    delete leaf1;
    delete leaf2;
    delete subtree;
    return 0;
}

Strategy Pattern: 

The Strategy Pattern defines a family of algorithms, encapsulates each one, and makes them interchangeable. This pattern allows the algorithm to vary independently from clients that use it.

#include<iostream>

using namespace std;

class Strategy {
public:
    virtual void Execute() = 0;
    virtual ~Strategy() {}
};

class ConcreteStrategyA : public Strategy {
public:
    void Execute() override {
        cout << "Executing Strategy A" << endl;
    }
};

class ConcreteStrategyB : public Strategy {
public:
    void Execute() override {
        cout << "Executing Strategy B" << endl;
    }
};

class Context {
public:
    void SetStrategy(Strategy* strategy) {
        strategy_ = strategy;
    }
    void ExecuteStrategy() {
        if (strategy_) {
            strategy_->Execute();
        }
    }
private:
    Strategy* strategy_;
};

int main() {
    Context context;
    Strategy* strategyA = new ConcreteStrategyA();
    Strategy* strategyB = new ConcreteStrategyB();

    context.SetStrategy(strategyA);
    context.ExecuteStrategy();

    context.SetStrategy(strategyB);
    context.ExecuteStrategy();

    delete strategyA;
    delete strategyB;
    return 0;
}

Observer Pattern:

The Observer Pattern defines a one-to-many dependency between objects so that when one object changes state, all its dependents are notified and updated automatically.

#include<iostream>
#include<vector>
#include<string>

using namespace std;

class Observer {
public:
    virtual void Update(const string& message) = 0;
    virtual ~Observer() {}
};

class Subject {
public:
    void Attach(Observer* observer) {
        observers_.push_back(observer);
    }

    void Detach(Observer* observer) {
        observers_.erase(remove(observers_.begin(), observers_.end(), observer), observers_.end());
    }

    void Notify(const string& message) {
        for (auto observer : observers_) {
            observer->Update(message);
        }
    }
private:
    vector<Observer*> observers_;
};

class ConcreteObserver : public Observer {
public:
    ConcreteObserver(const string& name) : name_(name) {}
    void Update(const string& message) override {
        cout << "Observer " << name_ << ": " << message << endl;
    }
private:
    string name_;
};

int main() {
    Subject subject;
    Observer* observer1 = new ConcreteObserver("Observer 1");
    Observer* observer2 = new ConcreteObserver("Observer 2");

    subject.Attach(observer1);
    subject.Attach(observer2);

    subject.Notify("Subject state has changed!");

    subject.Detach(observer1);
    subject.Notify("Subject state has changed again!");

    delete observer1;
    delete observer2;
    return 0;
}

Command Pattern:

The Command Pattern encapsulates a request as an object, thereby letting you parameterize clients with different requests, queue or log requests, and support undoable operations.

#include<iostream>
#include<vector>
#include<string>

using namespace std;

class Command {
public:
    virtual void Execute() = 0;
    virtual ~Command() {}
};

class Receiver {
public:
    void Action() {
        cout << "Receiver Action" << endl;
    }
};

class ConcreteCommand : public Command {
public:
    ConcreteCommand(Receiver* receiver) : receiver_(receiver) {}
    void Execute() override {
        receiver_->Action();
    }
private:
    Receiver* receiver_;
};

class Invoker {
public:
    void SetCommand(Command* command) {
        command_ = command;
    }
    void ExecuteCommand() {
        if (command_) {
            command_->Execute();
        }
    }
private:
    Command* command_;
};

int main() {
    Receiver receiver;
    Command* command = new ConcreteCommand(&receiver);
    Invoker invoker;

    invoker.SetCommand(command);
    invoker.ExecuteCommand();

    delete command;
    return 0;
}

Decorator Pattern:

The Decorator Pattern allows behavior to be added to an individual object, dynamically, without affecting the behavior of other objects from the same class.

#include<iostream>

using namespace std;

class Component {
public:
    virtual ~Component() {};
    virtual void Operation() = 0;
protected:
    Component() {};
};

class ConcreteComponent : public Component {
public:
    ConcreteComponent() {};
    void Operation() override {
        cout << "ConcreteComponent operation" << endl;
    }
    ~ConcreteComponent() {};
};

class Decorator : public Component {
public:
    Decorator(Component* com) : mCom(com) {};
    virtual ~Decorator() { delete mCom; };
    void Operation() override {};
protected:
    Component* mCom;
};

class ConcreteDecorator : public Decorator {
public:
    ConcreteDecorator(Component* com) : Decorator(com) {}
    ~ConcreteDecorator() {};
    void Operation() override {
        mCom->Operation();
        AddedBehavior();
    }
    void AddedBehavior() {
        cout << "ConcreteDecorator::AddedBehavior" << endl;
    }
};

int main() {
    Component* com = new ConcreteComponent();
    Decorator* dec = new ConcreteDecorator(com);
    dec->Operation();
    delete dec;
    return 0;
}

          

Chain of Responsibility Pattern: The Chain of Responsibility Pattern avoids coupling the sender of a request to its receiver by giving more than one object a chance to handle the request. This pattern chains the receiving objects and passes the request along the chain until an object handles it.

#include<iostream>

using namespace std;

class Handler {
public:
    virtual void SetNextHandler(Handler* handler) {
        next_handler_ = handler;
    }
    virtual void HandleRequest(int request) {
        if (next_handler_) {
            next_handler_->HandleRequest(request);
        }
    }
    virtual ~Handler() {}
protected:
    Handler* next_handler_ = nullptr;
};

class ConcreteHandler1 : public Handler {
public:
    void HandleRequest(int request) override {
        if (request < 10) {
            cout << "ConcreteHandler1 handled request: " << request << endl;
        } else if (next_handler_) {
            next_handler_->HandleRequest(request);
        }
    }
};

class ConcreteHandler2 : public Handler {
public:
    void HandleRequest(int request) override {
        if (request >= 10 && request < 20) {
            cout << "ConcreteHandler2 handled request: " << request << endl;
        } else if (next_handler_) {
            next_handler_->HandleRequest(request);
        }
    }
};

class ConcreteHandler3 : public Handler {
public:
    void HandleRequest(int request) override {
        if (request >= 20) {
            cout << "ConcreteHandler3 handled request: " << request << endl;
        } else if (next_handler_) {
            next_handler_->HandleRequest(request);
        }
    }
};

int main() {
    Handler* handler1 = new ConcreteHandler1();
    Handler* handler2 = new ConcreteHandler2();
    Handler* handler3 = new ConcreteHandler3();

    handler1->SetNextHandler(handler2);
    handler2->SetNextHandler(handler3);

    int requests[] = {5, 14, 22, 18, 3, 27};

    for (int request : requests) {
        handler1->HandleRequest(request);
    }

    delete handler1;
    delete handler2;
    delete handler3;

    return 0;
}

Bridge Pattern:

The Bridge Pattern decouples an abstraction from its implementation so that the two can vary independently.

#include<iostream>

using namespace std;

class AbstractionImp {
public:
    virtual ~AbstractionImp() {};
    virtual void Operation() = 0;
protected:
    AbstractionImp() {};
};

class Abstraction {
public:
    virtual ~Abstraction() {};
    virtual void Operation() = 0;
protected:
    Abstraction() {};
};

class RefinedAbstraction : public Abstraction {
public:
    RefinedAbstraction(AbstractionImp* imp) : mImp(imp) {};
    ~RefinedAbstraction() {};
    void Operation() override {
        mImp->Operation();
    }
private:
    AbstractionImp* mImp;
};

class ConcreteAbstractionImpA : public AbstractionImp {
public:
    ConcreteAbstractionImpA() {};
    ~ConcreteAbstractionImpA() {};
    void Operation() override {
        cout << "ConcreteAbstractionImpA" << endl;
    }
};

int main() {
    AbstractionImp* imp = new ConcreteAbstractionImpA();
    Abstraction* abs = new RefinedAbstraction(imp);
    abs->Operation();
    delete abs;
    delete imp;
    return 0;
}

These patterns are essential building blocks in software design. They provide a common language and proven solutions to recurring design problems, enabling developers to create more robust, maintainable, and scalable software systems.

N Queen Problem

N Queen Problem:

Solutions:

   The entire chessboard should be stored as an 1-dimensional array with the length of N, and is represented with A[N]. The value of the i-th element in A[i] represents the queen column position of the i-th row.

    For example:  A[5] = 3 represents a position of (5,3), the 5th row and the 3rd column.    

So, given arbitrary two rows: i,j (i!=j) and it corresponding two cols should be: A[i], A[j].

The conflict should happen in one of the cases:

1) A[i] == A[j]   column conflict case;

2) A[i] - A[j] == (i - j) or (j - i) two diagonal conflict cases;

So the first step is to find out if we can place a queen in (row, col) the algorithm should be:

[code]

bool OKtoPlace(int row, int col)
{ 
     for (int r = 0; r < row; r++) {
        if (A[r] == col || A[r] - col ==  row - r || A[r] - col == r - row)
               return false;
      }
      return true;
}

   The next step is how to find all possible solutions. This is a classic backtracking algorithm, there are two ways for implementation, recursive and non-recursive. and rescursive method is relatively simple, here is the workflow:

       

[code]
void Queen(int row)
{
    if (n == row) {     // if all row are done, print out result;                  
       count ++;       // a new possible solution found. 
       print_result();
    }
    else {
       for (int col = 0; col < N; col++) {    //try each col on the row
            if (can_place(row, col) {  // is it ok to set the queen on (row, col) ?
                   place(row, col);    // set the queen
                   queen(row + 1);     // move to the next row
             }
        }
}
 

Now combine the above two steps we get
Solution 1:

       

[code]

const int N = 8;
int A[N];
int count = 0;

void print_out(void){
    for(int r=0; r<N; r++){
        for(int c=0; c<N; c++){
            if(c == A[r]) cout<< "Q ";
            else cout<< "0 ";
        }
        cout<<endl;
    }
    cout<<endl;
}

bool OktoPlace(int row, int col)
{
    for (int r= 0; r<row; r++) {
        if (A[r] == col || A[r] -col == row -r || A[r] - col == row - r)
           return false;
    }
    return true;
}

void queen(int row)
{
    if(row == N) {
       count ++;
       print_out();
       return;
    }

    for (int col = 0; col < N; col++) {
         if(OktoPlace(row, col)) {
             A[row] = col;
             queen(row + 1);
        }
    }
}

int main(void)
{
    queen(0);
    cout << count << endl;
    return 0;
}

         

Now let's see if we can optimize the core algorithm.

Solution 2:

As we can see that in the above function OKtoPlace(int row, int col), the time complexity is O(N), we can reduce it to O(1) by introducing two extra 1-dimensional bool arrays: P, Q.  Each represents the diagonal elements of a position, so the sizeof P and Q is 2N-1. Now for any position [row, col] on the board, we need to check if any one of 
[col, row+col, N-1 +col + row]
has a conflict.

So for each given row, we can replace place() function with one compound statement:

[code]

bool C[N], P[2*N-1], Q[2*N-1];

C[col] = true; P[row+col] = true; Q[N-1+col-row] = true;

     

Same with can_place()function, for each given row, we can replace can_place() function with one compound statement:

[code]

if (C[col] == true || P[row+col] == true || Q[N-1+col-row] == true)  //conflict
else  // no conflict and good to place.    

So the whole program becomes:

[code]
const int N = 8;
bool C[N], P[2*N-1], Q[2*N-1];

int count = 0;

void queen(int row)
{
    if (row == N) {
       count ++;
       return;
    }
    for (int col = 0; col < N; col++) {
        if (C[col] || P[row + col] || Q[N-1 + col - row]) continue; //conflict on this position
        C[col] = true; P[row+col] = true; Q[N-1+col-row] = true;
        queen(row + 1);
        C[col] = false; P[row+col] = false; Q[N-1+col-row] = false;
    }
}

Solution 3:
we can replace these three 1 dimensional Boolean arrays with only three integers C,P,Q , each bit in [C,P,Q] represents [col, row+col, N-1 +col + row] like above:

So the whole program becomes:

[code]

const int N = 8;
int C, P, Q;

int count = 0;

void queen(int row)
{
    if (row == N) {
       count ++;
       return;
    }
    for (int col = 0; col < N; col++) {
        if ( (C>>col) &1|| P>>(row + col) & 1 || Q >> (N-1 + col - row) & 1) continue;
        C ^= (1 << col);  P ^=(1 << (row+col)); Q ^= ( 1 << (N-1+col-row));
        queen(row + 1);
        C ^= (1 << col);  P ^=(1 << (row+col)); Q ^= ( 1 << (N-1+col-row));
    }
}

Single Linked List

Reverse a linked list

Given a linked list, convert it in reverse order.

Solution:

[code]

void Reverse(Node * &Gptr)
{
     Node *prev = NULL;
     Node *cur = GPtr;
     Node *next;
     while(cur != NULL)
     {
         next = cur->nextptr;
         cur -> nextptr = prev;
         prev = cur;
         cur = next;
     }
     GPtr = prev;
}

[greeksforgreeks]Merge two sorted linked lists

Solution1: 
Using recursion

[code]

Node * MergeLists(Node *list1, Node *list2)
{
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;
    if (list1->value < list2 ->value) {
        list1->nextptr = MergeLists(list1->nextptr, list2);
        return list1;
    }
    else {
        list2->nextptr = MergeLists(list2->nextptr, list1);
        return list2;
    }
}

Solution2: similiar to Solution 1. However avoid using recursion, but this needs to understand some pointer tricks, use a pointer to pointers: tail and point to the current qualified node in either one of two lists.

[code]

Node *MergeLists(Node *list1, Node *list2)
{
      Node *mlist, **tail;
      for(mlist= NULL, tail = &mlist; list1 && list2; tail = &(*tail)->nextptr) 
      {
           if (list1->content < list2->content) {
               *tail = list1; list1 = list1->nextptr;
           } 
           else {
                *tail = list2; list2 = list2->nextptr;
           } 
      } 
      *tail = list1? list1: list2;
      return mlist; 
}

Solution3:

[code]

Node *MergeLists(Node *list1, Node *list2) 
{
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;

    Node *head;
    if (list1->content < list2->content) {
      head = list1;
    } else {
      head = list2;
      list2 = list1;
      list1 = head;
    }

    while(list1->nextptr != NULL) {
      if (list1->nextptr->content > list2->content) {
         Node *tmp = list1->nextptr;
         list1-> nextptr = list2;
         list2 = tmp;
       }
       list1 = list1->nextptr;
    }

    if (list1->nextptr == NULL) list1->nextptr = list2;
    return head;
}

Solution4: similar to Solution3, but easier to understand.

[code]

Node *MergeLists(Node  * list1,  Node *list2)
{
   if(list1 == NULL)
      return list2;
   else if (list2 == NULL)
      return list1;

   Node *head;
   if(list1->content < list2->content)
   {
      head = list1;
      list1 = list1->nextptr;
   } else
   {
      head = list2;
      list2 = list2->nextptr;
   }

   Node *current = head;
   while((list1 != NULL) ||( list2 != NULL))
   {
      if(list1 == NULL) {
         current->nextptr = list2;
         return head;
      }
      else if (list2 == NULL) {
         current->nextptr = list1;
         return head;
      }

      if(list1->content < list2->content)
      {
          current->nextptr = list1;
          list1 = list1->nextptr;
      }
      else
      {
          current->nextptr = list2;
          list2 = list2->nextptr;
      }
          current = current->nextptr;
   }

   current->nextptr = NULL; // needed to complete the tail of the merged list
   return head;

}

Find a mth to last element of a linked list

Given a singly linked list, find the mth-to-last element of the list. If m = 0, return the last element.

Solution 1: scan once to find the number of nodes n, and then scan again to find (n-m)-th element.

Solution 2: use two pointers, one is m element ahead and advance both at the same time.

[code]

Node *findMToLast(Node *head, int m) 
{
    Node *current, *mbehind;
    if (head == NULL) return NULL;
    
    current = head;
    for (int i= 0; i< m; i++) {
       if (current->next != NULL) current = current -> next;
       else return NULL;

    mbehind = head;
    while(current -> next != NULL) { 
        current = current -> next;
        mbehind = mbehind -> next;   
    }

    return mbehind;
}

Reverse a linked list in group.

Given a linked list, please reverse it in group, that is to say
for example:

1->2->3->4->5->6->7->8->9->10, 

after the function:

Node *reverseGroup(Node *head, int start, int len) 

reverseGroup(Node *head, 5, 3) is called,

it becomes 1->2->3->4->5->8->7->6->10. (assume that the 5th node and (5+3)th node are both in the list)

Solution:

[code]

Node *reverseGroup(Node *head, int start, int len)
{
    Node *r = head;
    while(r->next&& (--start)) r = r->next;
    if (!r->next) return NULL;
    Node *pre = head;
    Node *cur = r->next;
    Node *next = NULL;
    while(cur&&(len--)){
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    r->next->next = next;
    r->next = pre;
    return head;
}

Insert sort a linked list.

Solution:

[code]

Node *sortLinkList(Node *head)
{
     if(!head|| !head->next) return head;
     Node preNode(-1);
     preNode.next = head;
     Node *run = head;
     while(run&&run->next) {
         if(run->value < run->next->value) {
             run = run -> next;
             continue;
         }
         Node *pre = &preNode;
         while(pre->next->value < run->next->value) {
              pre = pre->next;
         }
//       swap(pre->next->value, run->next->value);  // swap also ok but it is not "insert"
         Node *tmp = pre->next;
         pre->next = run->next;
         run->next = run->next->next;
         pre->next->next = tmp;
     }
     return preNode.next;

}

Reorder nodes:

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4,5,6}, reorder it to {1,6,2,5,3,4}.

Solution:

1) using fast, slow pointer to split the lists into two linked lists;

2) reverse the second one;

3) alternately merge these two lists; 

[code]

Node * ReorderList(Node *p)
{
    Node *fast = p;
    Node *slow = p;
    Node *plist = p;
    while(fast->next&& fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
    }

    Node *rlist = reverseLinkedList(slow->next);   //refer to the above solutions.
    slow->next = NULL;

    // merge p and rlist

    Node preNode(-1);
    Node *vp = &preNode;

    while(plist&&rlist){
        vp->next = plist; plist=plist->next;
        vp = vp->next;
        vp->next = rlist; rlist=rlist->next;
        vp = vp ->next;
    }
    return preNode.next;
}

Tree & Binary Search Tree

[greeksforgreeks] A program to check if a binary tree is BST or not.

The following are the best solution greeksforgreeks provided.

Solution 1:

  Using in order traversal, and store the result in a auxiliary three element array, if the array is sorted in ascending order, the tree is BST.
  or we can optimization the space like:

[code]
bool isBST(Node *root)
{
     static struct Node *prev = NULL;
     if (root)
     {
         if(!isBST(root->left))
             return false;
         if ( prev != NULL && root->value <= prev->value)
             return false;
         prev = root;
         return isBST(root->right);
     }
     return true;

}

Find lowest common ancestor of two nodes in a binary tree.

Solution:

    Need to implement a helper function which find if a node is a child of the root node.

[code]

bool Has(Node *r, Node *p)
{
    if (r == NULL) return false;
    if (r == p) return true;
    return Has(r->left, p) || Has(r->right, p);
}

Node *LCA(Node *r, Node *p, Node *q)
{
    if (Has(r->left, p) && Has(r->left, q)) 
       return LCA(r->left, p, q);
    if (Has(r->right, p) && Has(r->right, q))
       return LCA(r-right, p, q);
    return r;
}

Find level of a node in a binary tree.

Solution:

[code]
int  findLevel(Node *r, Node *p, int level)
{
    if (root == NULL)
        return -1;
    if ( root == p ) return level;

    int ll = findLevel(root->left, p, level+1);
    if (ll != -1)  return ll;
    return findLevel(root->right, p, level+1);
}

Find Distance between two nodes in a binary tree.

Solution:
   formula: Dist(p,q) = Dist(r,p) + Dist(r,q) - 2*Dist(r, lca)

[Code] 
int Distance(Node *r, Node *p, Node *q) 
{ 
    Node *lc = LCA(r, p, q);
    int Distrp = findLevel(r, p, 0);
    int Distrq = findLevel(r, q, 0);
    int Distlca = findLevel(r, lc, 0);
    return Dist(r, p) + Dist(r, q) - 2* Dist(r, lc);
}

Binary tree iterative pre-order traversal.

Solution:

    using a auxiliary stack

[Code]
void Preorder(Node *r)
{
    stack<Node*>s;
    Node *c;
    s.push(r);
    while(!s.empty()) {
       Node *t = s.top();
       // print out the value of the Node
       cout << t->value << endl;
       s.pop();
       if(t->right) s.push(t->right);
       if(t->left) s.push(t->left);
    }
}

Binary tree iterative post-order traversal.

Solution:
    using two auxiliary stacks

[Code]

void Postorder(Node *r)
{
    Node *c;
    stack<Node*>s;
    stack<Node*>output;
    s.push(r);
    while(!s.empty()) {
       Node *t = s.top();
       output.push(t);
       s.pop();
       if(t->left) s.push(t->left);
       if(t->right) s.push(t->right);
    }
    while(!output.empty()) {
       cout << output.top()->value << endl;
       output.pop();
    }
}

Binary tree iterative in-order traversal.

Solution:
     using one auxiliary stack.
       

[code]
void Inorder(Node *r)
{
    Node *c = r;
    stack<Node *> s;
    while(1) {
      if(c) {
         s.push(c);
         c = c->left;
      }
      else{
         if (s.empty()) break;
         c = s.top();
         cout << c->value << endl;
         s.pop();
         c = c->right;
      }
    }
}

Traverse a binary tree level by level.

Solution:

    1. find the max height of the tree;

    2. print the tree level indexed by the level index;

[code]
int TreeHeight( Node *r)
{
    if (r == NULL) return 0;
    return max(TreeHeight(r->left), TreeHeight(r->right)) + 1; 
}

void printLevel(Node *r, int level)
{
     if (r==NULL) return;
     if ( level <0 ) return;
     if (level == 0)
          cout << r->value <<endl;
     printLevel(r->left, level - 1);
     printLevel(r->right, level - 1);
}

Find number of leaves in a binary tree.

Solution1:

[code]
int findLeaves(Node *r)
{
    if (r == NULL) return 0;
    if (r -> left == NULL && r->right == NULL) return 1; 
    return findLeaves(r->left) + findLeaves(r->right); 
}

Solution2: using static variable

[code]
int findLeaves(Node *r)
{
    static int count = 0;
    if (r == NULL) return count;
    if (r -> left == NULL && r->right == NULL) count ++; 
    return findLeaves(r->left) + findLeaves(r->right); 
}

Clone a binary tree

Solution: using recursive method;

[code]

struct Node {
      int value;
      Node *left;
      Node *right;
};
    
Node *cloneBinaryTree(Node *r)
{
    if (r==NULL) return NULL;
    Node *p = new Node;
    p->value = r->value;
    p->left = cloneBinaryTree(r->left);
    p->right = cloneBinaryTree(r->right);
    return p;
}