Day 13, 24, 35 Swap Nodes in Pairs, Search Insert Position

Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
--------
Solution #1
pre has the address of "next" of the previous node
pre can be replace by a ListNode* type.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode *saved;
        ListNode **pre;
        if (head != NULL && head->next != NULL) {
            saved = head->next;
            pre = &(head->next);
        }else {
            return head;
        }
        while (head != NULL && head->next != NULL) {
            *pre = head->next;
            ListNode *temp = head->next->next;
            head->next->next = head;
            head->next = temp;
            pre = &(head->next);
            head = temp;
            
        }
        return saved;
    }
};

Update on Sep-03-2014 
Solution #2, with dummy node

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        ListNode *dummy;
        dummy->next = head;
        ListNode *itr = dummy;
        
        while (head != NULL && head->next != NULL) {
                itr->next = head->next;
                ListNode *temp = head->next->next;
                head->next = temp;
                itr->next->next = head;
                itr = head;
                head = temp;
        }
        
        return dummy->next;
    }
};

Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
 -----------------------------------
 For #2, #3, if match is not found, compare target with A[start] to determine the final position

Solution #1 O(n) 

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        for(int i=0;i<n;i++) {
            if (A[i] >= target) {
                return i;
            }
        }
        return n;
        
    }
};

Solution #2 O(log n), recursive

class Solution {
public:
    int rec (int A[], int start, int end, int target) {
        
        if (start >= end) {
            if (A[start] >= target) {
                return start;
            }
            return start+1;
        }
        int mid = (start + end) / 2;
        if (A[mid] == target) {
            return mid;
        }
        if (A[mid] < target) {
            return rec(A,mid+1,end,target);
        }else {
            return rec(A,start,mid-1,target);
        }
    }
    int searchInsert(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        return rec(A,0,n-1,target);
    }
};

Solution #3 O(log n)

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int start = 0, end = n-1;
        
        while (start < end) {
            int mid = (start + end) / 2;
            if (A[mid] == target) {
                return mid;
            }
            if (A[mid] < target) {
                start = mid + 1;
            }else {
                end = mid - 1;
            }
        }
        if (A[start] >= target) {
            return start;
        }else {
            return start+1;
        }
    }
};

another version

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        int mid = n / 2;
        int left = 0, right = n - 1;
        
        while (left <= right) {
            mid = (left + right) / 2;
            if (A[mid] == target) {
                return mid;
            }
            if (A[mid] > target) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        
        return right + 1;
    }
};