Daily coding practice set #1

gistfile1.txt

void quicksort(int input[], int left, int right) {
    if(left < right) {
        int pivot = input[right];
        int leftIt = left;
        int rightIt = right; 
        
        while(leftIt < rightIt) {
            while(input[leftIt] < pivot) leftIt++;
            while(input[rightIt] > pivot) rightIt--;
        
            if(leftIt < rightIt) {
                int temp = input[leftIt];
                input[leftIt] = input[rightIt];
                input[rightIt] = temp;
              
                leftIt++;
                rightIt--;
            } else if(leftIt == rightIt) {
                leftIt++;
                rightIt--;
            }     
        }
        
        if(left < rightIt) quicksort(input, left, rightIt);
        if(leftIt < right) quicksort(input, leftIt, right);
    }
}

void binarysearch(int input[], int left, int right, int needle) {
    if(left > right) return -1;
    
    if(left <= right) {
        int mid = (left+right)/2;
    
        if(input[mid] == needle) return mid;
        else if(input[mid] < needle) binarysearch(input, mid+1, right, needle);
        else binarysearch(input, left, mid-1, needle);
    }
}

void selectionsort(int input[]) {
    int index, temp;
    
    for(int i=0; i<input.length()-1 ; i++) {
        index = i;
        for(int j=i ; j<input.length() ; j++) {
            if(input[index] > input[j]) index = j;
        }
        
        int temp = input[index];
        input[index] = input[i];
        input[i] = temp;
    }
}



class LinkedNode {
    public:
    int val;
    LinkedNode * next;
    LinkedNode * prev;
    
    LinkedNode(int val) {
       next = null;
       prev = null;
       val = val;
    }
};

//two runners O(n)
bool isPalindrome(LinkedNode* head) {
    LinkedNode* faster = head;
    LinkedNode* slower = head;
    
    while(faster != null) {
        faster = faster->next;
    }

    while(slower != faster) {
        if(slower->val != faster->val) return false;
        
        slower = slower->next;
        if(slower == faster) break; //node 갯수가 짝수일 경우
        faster = faster->prev;
    }
    
    return true;
}

void addNode(LinkedList* head, int val) { //add to the end of Linkedlist
    LinkedList *cur = head;
    LinkedList * node = new LinkedList(val);
    
    while(cur->next != NULL) cur = cur->next;
    
    cur->next = node;
}

LinkedList* searchNode(LinkedList* head, int val) {
    LinkedList *cur = head;
    
    while(cur != NULL) {
        if(cur->val == val) return cur;
        
        cur = cur->next;
    }
    
    return NULL;
}

void deleteNode(LinkedList* node) {
     Linkedlist* prev;
     
     if(node->prev != NULL) prev = node->prev;
     else {                     //node is head
         prev = node->next;
         prev->prev = NULL;
         
         delete node;
         
         return;
     }
    
     if(node->next != NULL) { //node is at the middle
         prev->next = node->next;
     } else {                 // node is tail
         prev->next = NULL;
     }
     
     delete node;
}