Linked List 鏈表

141. Linked List Cycle 判斷單鏈表中是否有環(huán)

使用到的數(shù)據(jù)結構：List
使用到的算法技巧：Tow Pointers 輔助指針

//設置兩個指針灯节，快指針每次走兩步，慢指針每次走一步，如果鏈表有環(huán)，快指針肯定會與慢指針重合
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL || head->next == NULL)
            return false;
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(slow != fast)
        {
            if(fast == NULL || fast->next == NULL)
                return false;
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};

這道題目同樣也可以用哈希表

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_map<ListNode*,bool> hashnode;
        while(head != NULL)
        {
            if(hashnode[head] == true)
                return true;
            hashnode[head] = true;
            head = head->next;
        }
        return false;
    }
};

160. Intersection of Two Linked Lists 找出兩個鏈表的交點

例子可參考題目中給出的：

160.jpg

使用到的數(shù)據(jù)結構：List

//例如上面例子中，求得A鏈表長度是5柳骄，B鏈表長度是6，兩者長度差是1，B鏈表結點先移動一步到b2丽啡，然后開始比較a1-b2、a2-b3硬猫，一直到c1-c1
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == NULL || headB == NULL)
            return NULL;
        int alength = 0;
        int blength = 0;
        ListNode* pa = headA;
        ListNode* pb = headB;
        
        while(pa != NULL)
        {
            alength++;
            pa = pa->next;
        }
        while(pb != NULL)
        {
            blength++;
            pb = pb->next;
        }
        
        pa = headA;
        pb = headB;
        
        int step = alength - blength;
        if(step >0)
        {
            int astep = step;
            while(astep--)
            {
                pa = pa->next;
            }
        }
        else
        {
            int bstep = -step;
            while(bstep--)
            {
                pb = pb->next;
            }
        }
        
        while(pa != pb && pa != NULL && pb != NULL)
        {
            pa = pa->next;
            pb = pb->next;
        }
        return pa;
        
    }
};

這道題目同樣可以用hash思想來解決

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        set<ListNode*> check;
        ListNode* pA = headA;
        while(pA != NULL)
        {
          //把鏈表A的結點依次放入set中
            check.insert(pA);
            pA = pA->next;
        }
        
        ListNode *pB = headB;
        while(pB != NULL)
        {
            //遍歷B鏈表补箍，查看每個結點在set中是否存在
            if(check.find(pB) != check.end())
                return pB;
            pB = pB->next;
        }
        return NULL;
    }
};

怎樣應對IT面試與筆試-（一）
怎樣應對IT面試與筆試-（二）
怎樣應對IT面試與筆試-（三）
怎樣應對IT面試與筆試-（四）
怎樣應對IT面試與筆試-（五）
怎樣應對IT面試與筆試-（五-1）
怎樣應對IT面試與筆試-（六）
怎樣應對IT面試與筆試-（七）
怎樣應對IT面試與筆試-（八）
怎樣應對IT面試與筆試-（九）
怎樣應對IT面試與筆試-（十）
怎樣應對IT面試與筆試-（十一）
怎樣應對IT面試與筆試-（十二）
怎樣應對IT面試與筆試-（十三）
怎樣應對IT面試與筆試-（十四）
怎樣應對IT面試與筆試-（十五）
怎樣應對IT面試與筆試-（十六）