代码随想录算法训练营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;}
};

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;}
};

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;}
};

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;}
};