链表
BM1 反转链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* ReverseList(ListNode* head) {
// write code here
ListNode* pre=nullptr;
ListNode* cur=head;
ListNode* nextnode=head->next;
while (cur) {
cur->next=pre;
pre=cur;
cur=nextnode;
nextnode=nextnode->next;
}
return pre;
}
};
|
BM2 链表内指定区间反转
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
| ListNode* reverseBetween(ListNode* head, int m, int n) {
// write code here
ListNode* dummy=new ListNode(0);
dummy->next=head;
ListNode* temp=dummy;
// 移动到m-1节点
for(int i=1;i<m;i++){
temp=temp->next;
}
ListNode* pre=nullptr;
ListNode* ghead=temp;
ListNode* cur=temp->next;
for(int i=m;i<=n;i++){
ListNode* nextnode=cur->next;
cur->next=pre;
pre=cur;
cur=nextnode;
}
ghead->next->next=cur;
ghead->next=pre;
return dummy->next;
}
|
BM3 链表中的节点每k个一组翻转
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
| ListNode* reverseKGroup(ListNode* head, int k) {
// write code here
ListNode* dummy=new ListNode(0);
dummy->next=head;
ListNode* pre=dummy;
ListNode* cur=dummy->next;
while (cur) {
ListNode* tail=pre;
for(int i=0;i<k;i++){
tail=tail->next;
if(tail==nullptr){
return dummy->next;
}
}
ListNode* nextgroup=tail->next;
tail->next=nullptr;
ListNode* newgroup=reverse(pre->next);
pre->next=newgroup;
cur->next=nextgroup;
pre=cur;
cur=nextgroup;
}
|
出口一（while 内部提前返回）：链表长度不是 $k$ 的倍数。当最后剩余节点不足 $k$ 个时，探测指针 tail 提前遇到 nullptr，触发提前返回。
出口二（while 外部末尾返回）：链表长度恰好是 $k$ 的倍数。最后一组完整的 $k$ 个节点全部成功翻转后，head 自然变为 nullptr 退出循环，由末尾统一释放内存并返回最终结果。