本文主要是介绍【leetcode】reverse Nodes in k-groups，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题：
给定一个链表的头指针，以及一个整数k，要求将链表按每k个为一组，组内进行链表逆置。少于k个的部分不做处理。
分析：
个人觉得问题的重点是熟悉链表的就地逆置操作，就是头插法。其他的考察点如果还有的话，就的细心程度。
实现：
void reverseList(ListNode *&pre, ListNode *head)
{ListNode *tail = NULL;while (head){ListNode* next = head->next;head->next = pre->next;pre->next = head;if(tail == NULL)tail = head;head = next;}pre = tail;
}
上面所示函数，实现将head指示的链表进行逆置链接在pre的后面。
void hh(ListNode*& pre, ListNode*head, int k){if(head == NULL || k <= 1){pre->next = head;return;}int dis = 1;ListNode* tail = head;while (dis < k && tail){++dis;tail = tail->next;}if(tail == NULL){pre->next = head;return;}ListNode *newhead = tail->next;tail->next = NULL;reverseList(pre, head);hh(pre, newhead, k);
}上面的函数，对给定的head 指示的链表，找出首个k个结点的链表区间，作为进行逆置的对象，并找到下一个逆置区间的开始结点，进行递归。
其实这里进行递归有点那个，唯一的解释就是懒。
ListNode *reverseKGroup(ListNode *head, int k) {ListNode* newHead = new ListNode(-1);ListNode* pre = newHead;hh(pre, head, k);return newHead->next;
}
下面的另外一种实现。
ListNode *reverseKGroup(ListNode *head, int k) {if (head == NULL || head->next == NULL || k == 1)return head;ListNode *new_head = new ListNode(-1);new_head->next = head;int visited_len = 0;ListNode *pre, *tail, *travel;pre = new_head;while (1){travel = pre;visited_len = 0;while (travel != NULL && visited_len < k) {travel = travel->next;if(travel)visited_len++;}if(visited_len < k) break;travel = travel->next;//the next begin position.ListNode *p = tail = pre->next;pre->next = travel;ListNode *q = p->next;do{p->next = pre->next;pre->next = p;p = q;if(p)q = p->next;}while(p != travel);pre = tail;}pre = new_head;new_head = new_head->next;delete pre;return new_head;}这篇关于【leetcode】reverse Nodes in k-groups的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
