Given a linked list, reverse the nodes of a linked list\u00a0k<\/em>\u00a0at a time and return its modified list.<\/p>\n k<\/em>\u00a0is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of\u00a0k<\/em>\u00a0then left-out nodes in the end should remain as it is.<\/p>\n Example:<\/strong><\/p>\n Given this linked list:\u00a0 For\u00a0k<\/em>\u00a0= 2, you should return:\u00a0 For\u00a0k<\/em>\u00a0= 3, you should return:\u00a0 Note:<\/strong><\/p>\n Two passes.<\/p>\n First pass, get the length of the list.<\/p>\n Second pass, swap in groups.<\/p>\n Time complexity: O(n)<\/p>\n Space complexity: O(1)<\/p>\n1->2->3->4->5<\/code><\/p>\n2->1->4->3->5<\/code><\/p>\n3->2->1->4->5<\/code><\/p>\n\n
Solution<\/strong><\/h1>\n
C++<\/h2>\n
\/\/ Author: Huahua\r\nclass Solution {\r\npublic:\r\n ListNode *reverseKGroup(ListNode *head, int k) {\r\n if (!head || k == 1) return head;\r\n ListNode dummy(0);\r\n dummy.next = head;\r\n int len = 1;\r\n while (head = head->next) len++;\r\n ListNode* pre = &dummy; \r\n for (int l = 0; l + k <= len; l += k) {\r\n ListNode* cur = pre->next;\r\n ListNode* nxt = cur->next;\r\n for (int i = 1; i < k; ++i) {\r\n cur->next = nxt->next;\r\n nxt->next = pre->next;\r\n pre->next = nxt;\r\n nxt = cur->next;\r\n }\r\n pre = cur;\r\n }\r\n return dummy.next;\r\n }\r\n};<\/pre>\n<\/div><\/div>\nRelated Problems<\/h1>\n