Rehashing

http://www.lintcode.com/en/problem/rehashing/

Discussion

典型的rehash算法，对每个listNode，找到在新hash table里面的位置，若该位置已经放了元素了，就放到队尾。

Solution

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param hashTable: A list of The first node of linked list
     * @return: A list of The first node of linked list which have twice size
     */    
    vector<ListNode*> rehashing(vector<ListNode*> hashTable) {
        // write your code here
        vector<ListNode*> result;
        if(hashTable.size() == 0) 
            return result;
        result = vector<ListNode*> (2*hashTable.size(), NULL);
        for(int i=0; i<hashTable.size(); i++) {
            helper(hashTable, result, i);
        }
        return result;
    }
    void helper(vector<ListNode*> &hashTable, vector<ListNode*> &rehashTable, int index) {
        ListNode* curNode = hashTable[index];
        int size = rehashTable.size();
        while(curNode != NULL) {
            int newPos = (curNode->val % size + size) % size;
            if(rehashTable[newPos] == NULL) {
                rehashTable[newPos] = new ListNode(curNode->val);
            } else {
                ListNode* tmp = rehashTable[newPos];
                while(tmp->next != NULL) {
                    tmp = tmp->next;
                }
                tmp->next = new ListNode(curNode->val);
            }
            curNode = curNode->next;
        }

    }
};