本文主要是介绍代码随想录算法训练营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;}
};
这篇关于代码随想录算法训练营31期day4,力扣24+19+02.07+142的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!