You may not alter the values in the nodes, only nodes itself may be changed. Only constant memory is allowed.
For example,
Given this linked list:
1->2->3->4->5
For k = 2, you should return:
2->1->4->3->5
For k = 3, you should return:
3->2->1->4->5
Solution: before do k-group reversion, we first need to check if the current linked list has at least one k-group. If not, we simply do nothing, otherwise we reverse it to get a new k-group, say k'. Then we recursively reverse the rest of nodes, and append the resulting linked list to the end of k'.
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *reverseKGroup(ListNode *head, int k) { // Note: The Solution object is instantiated only once and is reused by each test case. if(k<=0) return head; ListNode* cur = head; //check if the linked list has at least k nodes int c = 0; while(cur!=NULL && c<k){ cur=cur->next; ++c; } //the linked list has less than k nodes if(c<k) return head; //the linked list has at least k nodes ListNode* nxtHead = cur; //reverse the first k-group ListNode* pre = NULL; cur = head; c=0; while(c<k){ ListNode* nxt = cur->next; cur->next = pre; pre = cur; cur = nxt; ++c; } //do k-group reversion to the rest of nodes, and then append it to the reversed first k-group head->next = reverseKGroup(nxtHead, k); return pre; } };
No comments:
Post a Comment