BM3链表中的节点每k个一组翻转
1.题目
BM3 链表中的节点每k个一组翻转
将给出的链表中的节点每 k 个一组翻转,返回翻转后的链表
如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样
你不能更改节点中的值,只能更改节点本身。
![image-20230824140620807](/img/loading.gif)
2.解析
2.1 链表逆置
其他部分其实很好解决,基于链表逆置的代码(即逆置整个链表的代码)
我们只需要将每一个需要逆置的小区间的开头给记下来,交付给链表逆置就可以了。
1 2 3 4 5 6 7 8 9 10 11
| ListNode* reverseNode(ListNode* head) { if (head == nullptr || head->next == nullptr) { return head; }
ListNode* ans = reverseNode(head->next); head->next->next = head; head->next = nullptr; return ans; }
|
2.2 记录每个需要逆置的区间
比如如下部分代码,为了方便进行遍历和指针控制,我创建了一个头节点放置在了原本链表开头
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| ListNode phead(0); phead.next = head; ListNode* cur = &phead;
std::vector<ListNode*> begin_node_v,begin_node_prev_v; int index = k-1; int node_count = 0; while (cur != nullptr) { if(index+1 == k && cur != &phead){ begin_node_prev_v.push_back(cur); } else if (index == k) { begin_node_v.push_back(cur); index = 0; } cur = cur->next; index++; node_count ++; }
|
这里还创建了两个vector数组
begin_node_v
:待逆置区间的开头begin_node_prev_v
:待逆置区间的开头的上一个
下面是对这两个数组的说明,如果给出的示例是如下形式
那么两个数组分别存储了如下值
1 2
| begin_node_v: {1,3,5} begin_node_prev_v: {2,4}
|
这样一来,第一个数组实际上存放的是每个区间的开头,第二个数组存放的则是每个区间的结尾。逆置了之后:
- 第二个数组就是新区间的开头
- 第一个数组就是新区间的结尾
方便我们将逆置后的链表重新连起来!
2.3 抛弃无需逆置的区间
在上面的循环中,用了node_count
来计算了整个链表的长度,减1剔除我自己添加的头节点,就是原始链表的长度。
题目有个特殊要求:如果原始链表的长度并非k的整数倍,那么最后一段区域的链表是不需要逆置的
1 2 3 4
| 1 - 2 - 3 - 4 - 5 当k=3的时候,只需要逆置 1-2-3 4-5不需要逆置 3 - 2 - 1 - 4 - 5
|
在这种情况,用例和两个数组存放的节点如下
1 2 3 4
| 用例 {1,2,3,4,5},3
begin_node_v: {1,4} begin_node_prev_v: {3}
|
如果我们直接将begin_node_v
里面的节点交付给链表逆置函数,就会将4-5
这一段夜给逆置,最终返回的结果是3-2-1-5-4
,不符合题目要求!
所以在这种情况下,我们需要将4从第一个数组中删除!如果原视链表的节点数量已经小于k了,则也不需要逆置,直接返回即可。
1 2 3 4 5 6 7 8 9 10 11
| node_count --; if(node_count <k){ return head; }
ListNode* last_link = nullptr; if((node_count %k) != 0) { last_link = begin_node_v[begin_node_v.size()-1]; begin_node_v.pop_back(); }
|
另外,为了最终将这段么有逆置的链表和新链表连起来,我们还需用一个指针记录下这一段的开头;last_link
初始化为空是方便后续的判断,如果为空代表不存在这一段链表,不需要链接。
2.4 区间结束标识
为了标识每次逆置的结束符,我们还需要将待逆置的每一个小区间的末尾都改成nullptr
1 2 3 4
| for(auto&n:begin_node_prev_v){ n->next = nullptr; }
|
2.5 逆置和重新链接
上面的步骤都敲定了之后,我们就可以将第一个数组begin_node_v
的节点喂给链表逆置函数了,该逆置函数的返回值是新链表的开头。
1 2 3 4 5 6 7
| cur = &phead; for(auto& n:begin_node_v){ ListNode* ptr=reverseNode(n); cur->next = ptr; cur = n; }
|
这里说一下cur指针的作用,以用例{1,2,3,4,5},2
为栗子,此时begin_node_v
数组中存放的是{1,3,5}
- 初始化为phead
- 第一次循环,n指向的是1,cur指向的是phead;逆置结束后,ptr指向的是2,刚好就是新链表的开头,将cur的next链接为它,并将cur更新为1
- 第二次循环,n指向的是3,cur指向的是1;逆置结束后,ptr指向的是4,此时cur的next指向它,就是将1的next链接为4,再次更新cur为3。
- 第三次循环,n指向的是5,cur指向的是3;逆置结束后,将3的next链接为5,cur更新为5
- 循环结束
结束时,这个链表就已经完工了!我们只需要判断一下还没有剩下的没有逆置的节点,将其链接给begin_node_v
数组中的最后一个节点(也是逆置部分的最后一个节点)的next就可以了
1 2 3 4
| if(last_link !=nullptr){ begin_node_v[begin_node_v.size()-1]->next = last_link; }
|
3.完整代码
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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
| class Solution { public:
ListNode* reverseNode(ListNode* head) { if (head == nullptr || head->next == nullptr) { return head; }
ListNode* ans = reverseNode(head->next); head->next->next = head; head->next = nullptr; return ans; }
void cout_vector(std::vector<ListNode*>& begin_node_v) { for (auto& e : begin_node_v) { cout << e->val << " " ; } cout << endl; }
ListNode* reverseKGroup(ListNode* head, int k) { if (head == nullptr || head->next == nullptr || k <= 1) { return head; } ListNode phead(0); phead.next = head; ListNode* cur = &phead; std::vector<ListNode*> begin_node_v,begin_node_prev_v; int index = k-1; int node_count = 0; while (cur != nullptr) { if(index+1 == k && cur != &phead){ begin_node_prev_v.push_back(cur); } else if (index == k) { begin_node_v.push_back(cur); index = 0; } cur = cur->next; index++; node_count ++; } node_count --; if(node_count <k){ return head; } ListNode* last_link = nullptr; if((node_count %k) != 0) { last_link = begin_node_v[begin_node_v.size()-1]; begin_node_v.pop_back(); }
for(auto&n:begin_node_prev_v){ n->next = nullptr; } cur = &phead; for(auto& n:begin_node_v){ ListNode* ptr=reverseNode(n); cur->next = ptr; cur = n; } if(last_link !=nullptr){ begin_node_v[begin_node_v.size()-1]->next = last_link; } return phead.next; } };
|
通过截图
![image-20230824142627806](/img/loading.gif)