2021-03-23

141. Linked List Cycle

判断链表里是否有环。看似很简单的一道题，只需要长短指针一起遍历就完事了，但实际解决过程中还是被边界给狠狠地搞了几次。。。特别是[1], pos=-1 这个test case！！好多次runtime error都是因为将1->next赋值了，记住一定要先判断！！！！
【做法一】 12ms

public:
    bool hasCycle(ListNode *head) {
        ListNode *fast;
        fast = head;
        while(head){
            if (fast->next&&fast->next->next)
                fast = fast->next->next;
            else
                return false;
            
            if (fast == head)
                return true;
            head = head->next;
        }
        return false;
    }
};

【做法二】8ms

public:
    bool hasCycle(ListNode *head) {
        if (!head) return false;
        ListNode *low = head;
        ListNode *fast = head;
        
        while (fast->next&&fast->next->next){
            low = low->next;
            fast = fast->next->next;
            if (low==fast)
                return true;
            
        }
        return false;
            
    }
};

160. Intersection of Two Linked Lists

判断两个链表是否有交点。
笨方法挺长的，懒得写，刷评论区看到一个巧妙的办法，相当于是把两个链表连成了一个环，再在这个环上用两个指针扫描，很有想法！时间复杂度到底是o(m+n)还是o(n)还有待考察，以我现在的水平暂时还看不出来。

public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p1 = headA;
        ListNode *p2 = headB;
        while (p1 || p2){
            if(p1==p2) return p1;
            
            if(p1) p1 = p1->next;
            else p1 = headB;
            
            if(p2) p2 = p2->next;
            else p2 = headA;

        }
        return NULL;
        
        
    }
};