6.24 linkedListCycles & reorderList & LRU

• to do

1] Linked List Cycle

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

2] Linked List Cycle II

    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) return nullptr;
        ListNode* slow=head, *fast=head;
        
        while (fast && (fast=fast->next)) {
            slow = slow->next;
            fast = fast->next;
            if (slow == fast) {
                ListNode* slow2=head;
                while (slow != slow2) {
                    slow = slow->next;
                    slow2 = slow2->next;
                }
                return slow;
            }
        }
        return nullptr;
    }

3] Reorder List

    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* newh = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return newh;
    }
    
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;
        // partition list by mid point
        ListNode* slow=head;
        for (ListNode *fast=head; fast&&fast->next; 
             slow=slow->next, fast=fast->next->next) {}
        // reverse snd
        ListNode* snd = reverseList(slow->next);
        slow->next = NULL;
        // merge
        ListNode* l1Next, *sndNext;
        for (ListNode* l1=head; snd; l1=l1Next, snd=sndNext) {
            l1Next = l1->next;
            sndNext = snd->next;
            l1->next = snd;
            snd->next = l1Next;
        }
        return;
    }