首页 > 代码库 > leetcode - Reverse Nodes in k-Group
leetcode - Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
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
题目大意，按照k来对链表进行分组，然后对每组进行逆序，若该组的结点数比k小，则保持链表不变
个人思路：
1，先计算链表长度，记为length，结合k，可计算出组数group，然后就是对于每组结点做反转
2，对于反转，我设置了3个指针，preGroup指向前一个组的最后一个结点，current指向当前结点，pre指向当前结点的前一个结点，每次循环，都是把current指向的结点插入到preGroup指向的结点之后，直到该组的结点都遍历完
3，重新设置一下这3个指针，继续2的步骤，直到所有组都反转
代码：
1 #include <stddef.h> 2 3 struct ListNode 4 { 5 int val; 6 ListNode *next; 7 ListNode(int x) : val(x), next(NULL) {} 8 }; 9 10 class Solution {11 public:12 ListNode *reverseKGroup(ListNode *head, int k) {13 if (!head || k < 2)14 {15 return head;16 }17 18 ListNode dummy(-1);19 dummy.next = head;20 ListNode *current = dummy.next;21 int length = 0;22 23 while (current)24 {25 current = current->next;26 ++length;27 }28 29 int group = length / k;30 ListNode *preGroup = &dummy;31 ListNode *pre = &dummy;32 current = dummy.next;33 34 for (int i = 0; i < group; ++i)35 {36 preGroup = pre;37 pre = current;38 current = current->next;39 40 for (int j = 0; j < k - 1; ++j)41 {42 pre->next = current->next;43 current->next = preGroup->next;44 preGroup->next = current;45 46 current = pre->next;47 }48 }49 50 return dummy.next;51 }52 };
看了一下网上的思路，基本差不多（除了递归版的），关于反转，除了把current结点插入到preGroup之后，也可以把current结点插入到nextGroup（下一个组的头结点）之前，也算是拓展一下我的思维方式，防止思维定势
leetcode - Reverse Nodes in k-Group