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;
}

Two sum problem

Two Sum Problem

Given an array of integers, find two numbers such that they add up to a specific target number.The function twoSum should return two numbers such that they add up to the target. You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: value1 = 2, value2 = 7

1. bruteforce solution: 

The complexity is O(N^2):

[code]

bool bruteforce(vector<int> &v, int target, int &x, int &y)
{
    // O(N^2)
    for(int i = 0; i< v.size(); i++) {
       for(int j= i+1; j< v.size(); j++) {
            if(target == v[i] + v[j]) {
                 x = v[i];
                 y = v[j];
                 return true;
            }
       }
    }
    return false;
}

2. Sort and find solution: 

The Complexity is O(Nlog(N)) majorly because of sort complexity.

[code]

bool sortandfind(vector<int> &v, int target, int &x, int &y)
{
    sort(v.begin(), v.end());   // O(NlogN)
    int i = 0;
    int j = v.size() - 1;

    while(i<j) {
       if (v[i] + v[j] > target) j--;
       if (v[i] + v[j] < target) i++;
       if (v[i] + v[j] == target) {
           x = v[i]; y = v[j];
           return true;
       }
    }
    return false;
}

3. map and find solution:

The complexity is O(Nlog(N)) , the same as the above solution.

[code]
bool mapandfind(vector<int> &v, int target, int &x, int &y)
{
     map<int, int> Nap;    // O(Nlog(N))
     for( int i= 0; i< v.size(); i++) {
         Nap.insert(make_pair(target - v[i], v[i]));
     }

     for( int i= 0; i< v.size(); i++) {  // N
         if(Nap.find(v[i]) != Nap.end()) {  // O(log(N))
            x = v[i];
            y = target - v[i];
            return true;
         }
    }
    return false;
}

4. hash (unordered_map) map and find solution:

Just simply change to use hash-map (unordered_map) from above solution, the complexity becomes O(N).

[code]
bool unorderedmapandfind(vector<int> &v, int target, int &x, int &y)
{
     unordered_map<int, int> Nap;    
     for( int i= 0; i< v.size(); i++) {
         Nap.insert(make_pair(target - v[i], v[i]));
     }

     for( int i= 0; i< v.size(); i++) {  // N
         if(Nap.find(v[i]) != Nap.end()) {  // O(1)
            x = v[i];
            y = target - v[i];
            return true;
         }
    }
    return false;
}