算法通关村第二关—K个一组反转(黄金)

K个一组翻转链表

题目介绍

LeetCode25.给你一个链表，每k个节点一组进行翻转，请你返回翻转后的链表。k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。进阶：你可以设计一个只使用常数额外空间的算法来解决此问题吗？你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

1.头插法

如果虚拟结点理解了，会发现头插法比上面的穿针引线法更好理解，主要思路还是将其分成已经反转、正在反转和未反转三个部分。为了方便循环，我们可以先遍历一遍链表，统计一下元素数量len,确定要分几组n=len/k,然后再采用与前面青铜白银关一样的思路进行反转就可以了。下图表示的是反转结点5时的过程图：

代码实现：

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(k == 1) return head;
        ListNode node = head;
        int len = 0;
		//统计链表长度
        while(node != null){
            len++;
            node = node.next;
        }
        int sum = len / k; //统计反转次数
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
		//外层循环是链表反转的次数，内层循环是每次反转需要反转的元素的个数
        for(int i = 0; i < sum; i++){
            for(int j = 1; j <= k - 1; j++){
                ListNode next = cur.next;
                cur.next = next.next;
                next.next = pre.next;
                pre.next = next;
            }
            pre = cur;
            cur = cur.next;
        }
        return dummy.next;
    }
}

2.穿针引线法

这种思路与上面的穿针引线类似，我们根据图示一点点看：
首先，因为要分组反转，我们就一组一组的处理，将其分成已经反转、正在反转和未反转三个部分，同时为了好处理头结点，我们新建一个虚拟头结点。之后我们直接遍历，根据是否为K个找到四个关键位置，并用变量pre、start、end和next标记，如下：

接着我们就可以对上图中颜色部分进行反转了，我们如果end.next=null,那颜色部分可以直接复用前面的实现来完成反转。注意上图中指针的指向和几个变量的位置，hed表示传给反转方法的参数，结构如下
所示：

完成之后，我们要将裁下来的部分再缝到原始链表上，这就需要调整指针指向了，同样注意指针的指向：

代码实现：

public ListNode reverseKGroup(ListNode head, int k){
ListNode dummy = new ListNode (0)；
dummy.next = head;
ListNode pre = dummy;
ListNode end = dummy;
while (end.next != null){
//找到要处理的区间的末尾
for (int i= 0;i < k && end != null; i++){
end = end.next;
}
if (end == null){
break;
}
//将要处理的区间裁剪下来
ListNode start = pre.next;
ListNode next = end.next;
end. next = null;
//执行反转
pre.next = reverse(start);
/！上面pre.next和下面start.next两个指针是为了将反转的区间缝补回去
start.next = next;
//调整指针，为下一组做准备
pre = start;
end = pre;
}
return dummy.next;
}
//复用前面小节中的实现
private ListNode reverse(ListNode head){
ListNode pre = null;
ListNode curr = head;
while (curr != null){
ListNode next = curr.next;
curr.next = pre;
pre = curr:
curr = next;
}
return pre;
}