备赛蓝桥杯--算法题目(4)

1. 相交链表

160. 相交链表 - 力扣（LeetCode）

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {int cnt=0;ListNode* h1=headA;ListNode* h2=headB;while(h1->next){h1=h1->next;cnt++;}while(h2->next){h2=h2->next;cnt--;}if(h1!=h2){return nullptr;}if(cnt>0){h1=headA;h2=headB;}else{h1=headB;h2=headA;cnt=-cnt;}while(cnt){h1=h1->next;cnt--;}while(h1&&h2){if(h1==h2){break;}else{h1=h1->next;h2=h2->next;}}return h1;}
};

2. k个一组翻转链表

25. K 个一组翻转链表 - 力扣（LeetCode）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* start=head;ListNode* lastend=forend(start,k);if(lastend==nullptr){return head;}head=lastend;reverse(start,lastend);while(start->next){ListNode* ptr=start->next;lastend=forend(ptr,k);if(lastend==nullptr){break;}reverse(ptr,lastend);start->next=lastend;start=ptr;}return head;}void reverse(ListNode* head,ListNode* rear){ListNode* prev=nullptr,*next=nullptr,*ptr=head;rear=rear->next;while(ptr!=rear){next=ptr->next;ptr->next=prev;prev=ptr;ptr=next;}head->next=rear;}ListNode* forend(ListNode* head,int k){for(int i=1;head&&i<k;i++){head=head->next;}return head;}
};

3. 随机链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {if(head==nullptr){return nullptr;}Node* p1=head,*p2=head;while(p1){Node* ptr=new Node(p1->val);p2=p1->next;p1->next=ptr;ptr->next=p2;p1=p2;}p1=head;Node* ans=head->next;while(p1){Node* tmp=p1->next;p2=tmp->next;tmp->random=p1->random?p1->random->next:nullptr;p1=p2; }p1=head;while(p1){Node* tmp=p1->next;p2=tmp->next;p1->next=p2;tmp->next=p2?p2->next:nullptr;p1=p2;}return ans;}
};

4. 回文链表

234. 回文链表 - 力扣（LeetCode）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {ListNode* fast=head,* slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}fast=head;while(fast->next){fast=fast->next;}reverse(slow);slow=head;while(slow&&fast){if(slow->val!=fast->val){return false;}slow=slow->next;fast=fast->next;}return true;}void reverse(ListNode* head){ListNode* next=nullptr,*prev=nullptr;while(head){next=head->next;head->next=prev;prev=head;head=next;}}
};

5. 环形链表

LCR 022. 环形链表 II - 力扣（LeetCode）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head==nullptr){return nullptr;}ListNode* fast=head,* slow=head;while(fast->next&&fast->next->next){fast=fast->next->next;slow=slow->next;if(fast==slow){fast=head;while(fast!=slow){fast=fast->next;slow=slow->next;}return slow;}}return nullptr;}
};

6. 排序链表

LCR 077. 排序链表 - 力扣（LeetCode）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* start = nullptr;ListNode* end = nullptr;ListNode* findEnd(ListNode* s, int k) {while (s->next != nullptr && --k != 0) {s = s->next;}return s;}void merge(ListNode* l1, ListNode* r1, ListNode* l2, ListNode* r2) {ListNode* pre;if (l1->val <= l2->val) {start = l1;pre = l1;l1 = l1->next;} else {start = l2;pre = l2;l2 = l2->next;}while (l1 != nullptr && l2 != nullptr) {if (l1->val <= l2->val) {pre->next = l1;pre = l1;l1 = l1->next;} else {pre->next = l2;pre = l2;l2 = l2->next;}}if (l1 != nullptr) {pre->next = l1;end = r1;} else {pre->next = l2;end = r2;}}ListNode* sortList(ListNode* head) {int n = 0;ListNode* cur = head;while (cur != nullptr) {n++;cur = cur->next;}ListNode *l1, *r1, *l2, *r2, *next, *lastTeamEnd;for (int step = 1; step < n; step <<= 1) {l1 = head;r1 = findEnd(l1, step);l2 = r1->next;r2 = findEnd(l2, step);next = r2->next;r1->next = nullptr;r2->next = nullptr;merge(l1, r1, l2, r2);head = start;lastTeamEnd = end;while (next != nullptr) {l1 = next;r1 = findEnd(l1, step);l2 = r1->next;if (l2 == nullptr) {lastTeamEnd->next = l1;break;}r2 = findEnd(l2, step);next = r2->next;r1->next = nullptr;r2->next = nullptr;merge(l1, r1, l2, r2);lastTeamEnd->next = start;lastTeamEnd = end;}}return head;}
};