Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.
Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10?5??) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
Then N lines follow, each describes a node in the format:
Address Data Next
where Address is the position of the node, Data is an integer, and Next is the position of the next node.
Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
Sample Output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
#include<bits/stdc++.h>
using namespace std;struct ListNode{int addr;int data;ListNode *next;ListNode(int x,int y) : addr(x),data(y), next(NULL) {}
};ListNode* creatList(int headAddr,int& n){vector<vector<int>> arr(100005,vector<int>(2,0));int addr,data,addrNext;for(int i=0;i<n;i++){cin>>addr>>data>>addrNext;arr[addr][0]=data;arr[addr][1]=addrNext;}n=1;ListNode *head=new ListNode(headAddr,arr[headAddr][0]);ListNode *p=head;for(int i=headAddr;arr[i][1]!=-1;i=arr[i][1]){int next=arr[i][1];ListNode *node=new ListNode(next,arr[next][0]);n++;p->next=node;p=p->next;}return head;
}ListNode* reverseKGroup(ListNode* head, int k,int count) {//保证有两个以上的元素,并且k>1if(head==NULL || head->next==NULL || k==1) return head;ListNode* dummyHead=new ListNode(0,0);ListNode* dummy=dummyHead;dummy->next=head;ListNode* pre=head;ListNode* cur=head;while(count>=k){cur=pre->next;ListNode* tmp=NULL;for(int i=1;i<k;i++){tmp=cur->next;cur->next=pre;pre=cur;cur=tmp;}tmp=dummy->next;dummy->next=pre;tmp->next=cur;dummy=tmp;pre=cur;count-=k;}dummy=dummyHead->next;delete dummyHead;return dummy;
}void printList(ListNode* head) {while (head) {if (head->next) {cout << fixed << setw(5) << setfill('0')<< head->addr;cout << " " << head->data<<" ";cout << fixed << setw(5) << setfill('0')<< head->next->addr << endl;}else {cout << fixed << setw(5) << setfill('0') << head->addr;cout << " " << head->data << " " << -1 << endl;}head = head->next;}
}int main(){int headAddr,n,k;cin>>headAddr>>n>>k;ListNode *head=creatList(headAddr,n);head=reverseKGroup(head,k,n);printList(head);return 0;
}
注：第5个测试案例可能会超时，多提交几次就通过了，400ms的限制有点严格。