假设我们有一个链表,我们必须一次反转链表k的节点并返回其修改后的列表。这里k是一个正整数,并且小于或等于链表的长度。因此,如果节点数不是k的倍数,那么最后剩下的节点应保持原样。
因此,如果链接列表类似于[1,2,3,4,5,6,7]并且k为3,则结果将为[3,2,1,6,5,4,7]。
为了解决这个问题,我们将遵循以下步骤-
定义一个名为的方法solve()
,它将采用链表的头部,采用partCount和k
如果partCount为0,则返回head
newHead:= head,上一页:= null,x:= k
而newHead不为null且x不为0
temp:= newHead的下一个,nextHead的下一个:=上一个
上一页:= newHead,newHead:= temp
下一首:= solve(newHead,partCount – 1,k)
返回上一页
从主要方法中执行以下操作-
返回solve(链表的头,链表的长度/ k,k)
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } void print_vector(vector<vector<auto>> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << "["; for(int j = 0; j <v[i].size(); j++){ cout << v[i][j] << ", "; } cout << "],"; } cout << "]"<<endl; } class ListNode{ public: int val; ListNode *next; ListNode(int data){ val = data; next = NULL; } }; ListNode *make_list(vector<int> v){ ListNode *head = new ListNode(v[0]); for(int i = 1; i<v.size(); i++){ ListNode *ptr = head; while(ptr->next != NULL){ ptr = ptr->next; } ptr->next = new ListNode(v[i]); } return head; } void print_list(ListNode *head){ ListNode *ptr = head; cout << "["; while(ptr){ cout << ptr->val << ", "; ptr = ptr->next; } cout << "]" << endl; } class Solution { public: ListNode* solve(ListNode* head, int partitionCount, int k){ if(partitionCount == 0)return head; ListNode *newHead = head; ListNode* prev = NULL; ListNode* temp; int x = k; while(newHead && x--){ temp = newHead->next; newHead->next = prev; prev = newHead; newHead = temp; } head->next = solve(newHead, partitionCount - 1, k); return prev; } int calcLength(ListNode* head){ int len = 0; ListNode* curr = head; while(curr){ len++; curr = curr->next; } return len; } ListNode* reverseKGroup(ListNode* head, int k) { int length = calcLength(head); return solve(head, length / k, k); } }; main(){ vector<int> v = {1,2,3,4,5,6,7}; ListNode *head = make_list(v); Solution ob; print_list(ob.reverseKGroup(head, 3)); }
1,2,3,4,5,6,7 3
输出结果
[3, 2, 1, 6, 5, 4, 7, ]