嵌入式软件开发面试问题_自由设计师是什么意思_四川省人民政府_企业宣传片视频

目录

LeetCode876 链表的中间节点

Leetcode141 环形链表

LeetCode142 环形链表II

LeetCode143 重排链表

---

LeetCode876 链表的中间节点

初始化时快慢指针同时指向head，快指针移动两步，慢指针移动两步。

/*** 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* middleNode(ListNode* head) {ListNode* fast=head;ListNode* slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow;}
};

Leetcode141 环形链表

 

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

LeetCode142 环形链表II

 

 

/*** 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) {ListNode* fast=head;ListNode* slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){while(head!=slow){head=head->next;slow=slow->next;}return slow;}}return nullptr;}
};

 

LeetCode143 重排链表

/*** 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* reverse(ListNode* head){ListNode* pre=nullptr;ListNode* cur=head;while(cur){ListNode* nex=cur->next;cur->next=pre;pre=cur;cur=nex;}return pre;}void reorderList(ListNode* head) {ListNode* fast=head;ListNode* slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}ListNode* last=reverse(slow);ListNode* r1=head;ListNode* r2=last;while(r2->next){ListNode* nex1=r1->next;ListNode* nex2=r2->next;r2->next=r1->next;r1->next=r2;r1=nex1;r2=nex2;}}
};