[Leetcode] Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Analysis:

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node == NULL)
            return NULL;
            
        //use BFS to visit all nodes
        queue<UndirectedGraphNode*> q;
        //use hash table to marked as visited
        map<UndirectedGraphNode*, UndirectedGraphNode*> m;
        m[node] = new UndirectedGraphNode(node->label);
        q.push(node);
        while(!q.empty())
        {
            UndirectedGraphNode* t = q.front();
            q.pop();
            for(int i=0; i<t->neighbors.size(); i++)
            {
                UndirectedGraphNode* n = t->neighbors[i];
                //if not visited before, added to the hash table and queue
                if (m.find(n) == m.end())
                {
                    m[n] = new UndirectedGraphNode(n->label);
                    q.push(n);
                }
                
                m[t]->neighbors.push_back(m[n]);
            }
        }
        
        return m[node];
    }
};

[Leetcode] Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

class Solution {
public:
    int singleNumber(int A[], int n) {
        int ret = A[0];
        for(int i=1; i<n; i++)
        {
            ret = ret ^ A[i];
        }
        return ret;
    }
};

[Leetcode] Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Analysis:

Count the numbers of each bit for all integers and the bit which is not times of 3 is the bit of the integer appears once.

class Solution {
public:
    int singleNumber(int A[], int n) {
        vector<int> nums(32,0);
        for(int i=0; i<n; i++)
        {
            int num = A[i];
            for(int j=0; j<32;j++)
            {
                nums[j] += (num >> j) & 0x1;
            }
        }
        
        int ret = 0;
        for(int i=0; i<32;i++)
        {
            if (nums[i] % 3)
                ret = ret | (0x1 << i);
        }       
        
        return ret;
    }
};

[Leetcode] Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Analysis:

基本思想：拷贝每个node，使得1->2->3变成1->1->2->2->3->3.然后fix random pointer，因为每个拷贝的node的random都是原来node的下一个，除非是NULL。最后从list中分离拷贝node

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if (head == NULL)
            return head;
        //duplicate node
        RandomListNode* curr = head;
        while(curr != NULL)
        {
            RandomListNode* next = curr->next;
            RandomListNode* newNode = new RandomListNode(curr->label);
            curr->next = newNode;
            newNode->next = next;
            curr = next;
        }
        
        //copy random
        curr = head;
        while(curr != NULL)
        {
            if (curr->random != NULL)
                curr->next->random = curr->random->next;
            curr = curr->next->next;
        }
        
        //split the list
        RandomListNode* newHead = NULL;
        RandomListNode* p = NULL;
        curr = head;
        while(curr != NULL)
        {
            if (p == NULL)
            {
                newHead = curr->next;
                p = curr->next;
            }
            else
            {
                p->next = curr->next;
                p = p->next;
            }
            curr->next = curr->next->next;
            curr = curr->next;
        }
        
        return newHead;
        
    }
};

[Leetcode] Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Analysis:

Use a fast and slow pointer and list has a cycle if two pointers encounter.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
                break;
        }
        
        return fast != NULL && fast->next != NULL;
    }
};

[Leetcode] Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

Analysis:

分析：以上图为例，假设从开始点1到cycle开始点4的距离为h，假设fast和slow在点7碰到而且从4到7的距离为a，整个cycle的长度为c；假设fast走了n圈，slow走了m圈，fast走的是slow的两倍那么我们就有

H + n*c + a = 2 ( h + m*c + a)

==>

(n-m)c = h + a

也就是说，如果两个指针slow从7开始走，p从head开始走，那么最终他们还是会碰到7这点。因为slow和p的速度是一样的，所以，他们的4，5，6这几点肯定是重合的，那么第一个重合的点就是cycle开始的点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
                break;
        }
        
        if (fast == NULL || fast->next == NULL)
            return NULL;
            
        slow = head;
        while(fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        
        return slow;
        
    }
};

[Leetcode] Reorder List

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}, reorder it to {1,4,2,3}.

Analysis:

1. Split into two list: L0→L1→... and ...→Ln-1→Ln

2. Reverse ...→Ln-1→Ln into Ln→Ln-1→...

3. Merge  L0→L1→... and Ln→Ln-1→... into one list

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    ListNode* reverseNode(ListNode* head)
    {
        ListNode* prev = NULL;
        ListNode* curr = head;
        while(curr != NULL)
        {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }


    void reorderList(ListNode *head) {
        if (head == NULL || head->next == NULL)
            return;
        //split
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* prev = NULL;
        while(fast != NULL && fast->next != NULL)
        {
            prev = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        //reverse
        prev->next = NULL;
        ListNode* h2 = reverseNode(slow);
        
        //merge
        ListNode* h1= head;
        while(h1 != NULL && h2 != NULL)
        {
            ListNode* h1Next = h1->next;
            ListNode* h2Next = h2->next;
            h1->next = h2;
            if (h1Next != NULL)
            {
                h2->next = h1Next;
            }
            h1 = h1Next;
            h2 = h2Next;
        }
    }
};