876. 链表的中间结点
代码
/**
* 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 * slow = head, * fast = head;
while(fast && fast -> next){
slow = slow->next;
fast = fast->next->next;
}//找中间节点
return slow;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
876. 链表的中间结点
代码
141. 环形链表
代码
/**
* 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 * slow = head, * fast = head;
while(fast && fast -> next){
slow = slow->next;
fast = fast -> next -> next;
if(slow == fast) return true;
}
return false;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
142. 环形链表 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 * slow = head, *fast = head;
while(fast && fast -> next){
slow = slow -> next;
fast = fast -> next -> next;
if(slow == fast){
while(head != slow){
head = head->next;
slow = slow -> next;
}
return slow;
}
}
return NULL;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
LCR 026. 重排链表
代码
/**
* 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:
void reorderList(ListNode* head) {
ListNode * slow = head, * fast = head;
while(fast && fast -> next){
slow = slow->next;
fast = fast->next->next;
}//找中间节点
ListNode * prev = nullptr, * cur = slow;
while(cur){
ListNode * tp = cur -> next;
cur -> next = prev;
prev = cur;
cur = tp;
}//反转后半段链表
ListNode * head2 = prev, *head1 = head;
while(head2 -> next){
ListNode * tp1 = head1->next, * tp2 = head2 -> next;
head2->next = head1->next;
head1->next = head2;
head1 = tp1;
head2 = tp2;
}//令交错指向,最终head2的下一个为空结束
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35