Sword finger offer special assault edition day 7

The finger of the sword Offer II 021. Delete the last of the linked list n Nodes
Simple linked list preprocessing length , You can also use the stack or Double pointer （ $i$ Go ahead $n$ individual , then $i$ And $j$ Walk together until $i$ To null pointer ） To do it

class Solution {
    
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    
        int sz = 0;
        ListNode res(0,head), *t = head;
        while(t){
    
            sz++; 
            t = t->next;
        }
        t = head; 
        ListNode *tmp = &res;
        for(int i = 0; i < sz-n; i++, t = t->next, tmp = tmp->next) ;
        tmp->next = t->next;
        return res.next;
    }
};

---

The finger of the sword Offer II 022. The entry node of a link in a list
Hash table practices

class Solution {
    
public:
    ListNode *detectCycle(ListNode *head) {
    
        ListNode *t = head, flag(0);
        unordered_map<ListNode*,bool> um;
        while(t) {
    
            if(!um.count(t)) um[t] = true;
            else return t;
            t = t->next;
        }
        return nullptr;
    }
};

Fast and slow pointer practice
$fast$ Take two steps ,$slow$ Take a step , until $fast$ And $slow$ Meeting shows that there are links in the linked list .
When we meet , Through mathematical relations $slow$ To ring entry point +n The distance of the ring is just equal to the distance from the chain head to the ring entry point

class Solution {
    
public:
    ListNode *detectCycle(ListNode *head) {
    
        ListNode *fast = head, *slow = head;
        while(fast) {
    
            slow = slow->next;
            if(fast->next == nullptr) return nullptr;
            fast = fast->next->next;
            if(fast == slow) {
    
                auto ptr = head;
                while(ptr != slow) {
    
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }   
        return nullptr;     
    }
};

---

The finger of the sword Offer II 023. The first coincident node of two linked lists

1. t1 Walk the A, go B
2. t2 Walk the B, go A

Situation 1 、 Disjoint
They will all arrive at the same time nullptr And end the cycle .
Situation two 、 The intersection
Finally, we reach the intersection at the same time

class Solution {
    
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    
        ListNode *t1 = headA, *t2 = headB;
        while(t1 != t2){
    
            t1 = t1 == nullptr? headB: t1->next;
            t2 = t2 == nullptr? headA: t2->next;
        }
        return t1;
    }
};