代码随想录算法训练营31期day4,力扣24+19+02.07+142

24，动指针

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
    	//建立虚拟头结点
        auto dummy=new ListNode(-1);
        dummy->next=head;
        for(auto p=dummy;p->next&&p->next->next;){
            auto a=p->next;
            auto b=a->next;
            p->next=b;
            a->next=b->next;
            b->next=a;
            p=a;
        }
        return dummy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

19

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        auto dummy=new ListNode(-1);
        dummy->next=head;
        int len=0;
        for(auto p=dummy;p;p=p->next) len++;
        for(auto p=dummy;p;p=p->next){
            len--;//先减，因为需要倒数第N个的前面一个来改变指针
            if(n==len){
                p->next=p->next->next;
                break;
            }
        }
        return dummy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

02.07
找两个链表相交的第一个节点，可以先遍历链表B，每遍历一个节点，再遍历链表A看是否有相等的节点，如果有直接返回此节点即可。如果没有继续循环

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto p1=headA;
        while(p1){
            auto p2=headB;
            while(p2){
                if(p1==p2) return p1;
                p2=p2->next;//将B链表的所有节点与A链表第一个节点比较看是否匹配
            }
            p1=p1->next;
        }
        return NULL;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

142
快慢指针

第一次相遇在c点，slow退回y步到b，quick退回2y步到c撇，由于，这一定是上一步走到的位置，所以，可以理解成，在这一步，slow走了x到b，quick走了2x到c撇，圈的长度就是x+y，再回到相遇点c，此时slow和quick均在c点，c到b距离是x，和a到b一样，所以把送slow放回头结点，quick不动，还在c点，各进一步，最终第一次会相遇在b点

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        auto slow=head;
        auto quick=head;
        while(quick&&quick->next){
            slow=slow->next;
            quick=quick->next->next;
            if(slow==quick){
                slow=head;
                while(slow!=quick){
                    slow=slow->next;
                    quick=quick->next;
                }
                return slow;
            }
        }
        return NULL;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20