问题：

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

 

官方难度：

Hard

 

翻译：

给定一个链表，将节点每k项倒序链接，并且返回头结点。如果剩余链表不足k项，保持原状不动。

算法必须使用恒定的空间，且不能只交换节点的数据，必须交换节点。

 

例子：

给定链表：1->2->3->4->5。

K=2，返回链表：2->1->4->3->5。

K=3，返回链表：3->2->1->4->5。

 

1. 这是No.024（Swap Nodes in Pairs）的深入研究。
2. 需要交换具体的节点，而不是节点存储的数据。
3. 首先要确定链表的长度size和返回的第一个节点first。
4. 维护上一个节点last和当前节点current。
5. 根据入参k和链表长度size建立while循环，每次循环结束前size-k。
6. 循环内部，先将待处理的节点，放入数组。
7. 将last节点的next指向数组最后一个元素，然后倒序将数组中的节点的next指向数组上一个元素，最后将数组第一个元素节点next指向当前节点current。
8. 更新上一个节点值last。
9. 入参检查，第一个节点head为null，或k<2时，直接返回head。

 

解题代码（交换数据）：

1     // 交换数据 2     public static ListNode reverseKGroupVal(ListNode head, int k) { 3         if (head == null || k < 2) { 4             return head; 5         } 6         // 获取链表的长度 7         ListNode check = head; 8         int size = 0; 9         while (check != null) {10             size++;11             check = check.next;12         }13         ListNode current = head;14         ListNode[] reverse = new ListNode[k];15         while (size > k - 1) {16             // 倒序的节点数组，同时将 current 指向下一次倒序的节点开始位置17             for (int i = 0; i < k; i++) {18                 reverse[i] = current;19                 current = current.next;20             }21             // 交换至一半结束22             for (int i = 0; i < (k >>> 1); i++) {23                 reverse[i].val = reverse[i].val + reverse[k - 1 - i].val - (reverse[k - 1 - i].val = reverse[i].val);24             }25             size -= k;26         }27         return head;28     }

 

解题代码（交换节点）：

1     // 交换节点 2     public static ListNode reverseKGroup(ListNode head, int k) { 3         if (head == null || k < 2) { 4             return head; 5         } 6         // 获取链表的长度 7         ListNode check = head; 8         int size = 0; 9         while (check != null) {10             size++;11             check = check.next;12         }13         // 确定返回的头节点14         ListNode first = head;15         if (k <= size) {16             for (int i = 1; i < k; i++) {17                 first = first.next;18             }19         }20         // 当前节点和上一个节点21         ListNode current = head;22         ListNode last = new ListNode(0);23         ListNode[] reverse = new ListNode[k];24         while (size > k - 1) {25             for (int i = 0; i < k; i++) {26                 reverse[i] = current;27                 current = current.next;28             }29             // 倒序赋值30             last.next = reverse[k - 1];31             for (int i = k - 1; i > 0; i--) {32                 reverse[i].next = reverse[i - 1];33             }34             reverse[0].next = current;35             // 更新上一个节点36             last = reverse[0];37             size -= k;38         }39         return first;40     }

 

相关链接：

 

PS：如有不正确或提高效率的方法，欢迎留言，谢谢！