给你链表的头节点 head ，每?k?个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是?k?的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5?示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000?解题思路：
本题是LeetCode 第24题两两交换链表中的节点swapPairs_萝萝荦荦的博客-CSDN博客的进阶版本
将整个链表分割成若干个长度为k的子链表来出来
参数设置：
curHead 当前正在处理的子链表的头节点
curTail 当前正常处理的子链表的尾部节点
thisHead 最终需要返回的链表的头节点
lastTail 上一个处理的链表的尾部节点
下图为各个指针的初始位置?
首先找到当前需要处理的子链表的尾节点，此节点通过重当前节点往下数k-1个节点获得。
如果在遍历过程中，走到了空节点，说明链表已经处理完，直接把当前的头节点返回即可。
下图为处理第一段子链表时候，找到子链表的尾节点过程：
?到当前步骤为止，我们已经控制了子链表的头和尾，我们现在要做的事处理子链表中间的情况。
设置一些中间指针：
nextHead 下一个子链表的头节点
n1 设置为当前处理段的头部
n2 为n1的下一个位置
n3 为n2的下一个位置
?
?
?
?
?
?如果thisHead == head 说明我们从来没更改过这个值，我们将其设置为curTail
如果lastTail有值，说明这不是第一段子链表，将上一段的尾巴连接到这一段的头
?
到此为止，一段子链表已经处理好了，我们开始循环往复处理下一段?
Java代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(k==1){
return head;
}
ListNode curHead = head;
ListNode curTail = head;
ListNode thisHead = head;
ListNode lastTail = null;
while(curHead!=null){
for(int i=0; i<k-1; i++){
if(curTail!=null){
curTail = curTail.next;
}else{
return thisHead;
}
}
if(curTail==null){
return thisHead;
}
ListNode nextHead = curTail.next;
curTail.next = null;
ListNode n1 = curHead;
ListNode n2 = curHead.next;
n1.next = null;
ListNode n3;
while(n2!=null){
n3 = n2.next;
n2.next = n1;
n1 = n2;
n2 = n3;
}
curHead.next = nextHead;
if(thisHead==head){
thisHead = curTail;
}
if(lastTail!=null){
lastTail.next = curTail;
}
lastTail = curHead;
curHead = nextHead;
curTail = nextHead;
}
return thisHead;
}
}?Python代码
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if k == 1:
return head
curHead = head
curTail = head
thisHead = head
lastTail = None
while curHead is not None:
for i in range(k-1):
if curTail is not None:
curTail = curTail.next
else:
return thisHead
if curTail is None:
return thisHead
nextHead = curTail.next
curTail.next = None
n1 = curHead
n2 = curHead.next
n1.next = None
while n2 is not None:
n3 = n2.next
n2.next = n1
n1 = n2
n2 = n3
curHead.next = nextHead
if thisHead == head:
thisHead = curTail
if lastTail is not None:
lastTail.next = curTail
lastTail = curHead
curHead = nextHead
curTail = nextHead
return thisHead