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