算法为编程语言的基础

技术面试中，面试官一般会先就你所应聘的岗位进行相关知识的考察，也叫基础知识和业务逻辑面试。只要你回答的不是特别特别差，面试官通常会说：“咱们写个代码吧”，这个时候就开始了算法面试。也就是说，一轮技术面试=基础知识和业务逻辑面试+算法面试。

一次字节跳动面试的感慨

前段时间，我曾面试字节跳动，面试官的一道算法题算是把我给难住了，给大家还原当时的面试场景如下：

面试官：给定单链表的头结点 head，实现一个调整链表的函数，从链表尾部开始，以 K 个结点为一组进行逆序翻转，头部剩余结点不足一组时，不需要翻转。（不能使用队列或者栈作为辅助）

但是这个算法题困扰了我很久，一直苦苦得不出答案。最后还是在面试官的提醒下才知晓正确的答案。

正确答案如下：

我们先定义一个 reverseKGroupPlus() 方法

public ListNode reverseKGroupPlus(ListNode head, int k) { 
 if (head == null || k <= 1) return head; 
 
 // 计算原始链表长度 
 int length = linkedLength(head); 
 if (length < k) 
 return head; 
 // 计算 offset 
 int offsetIndex = length % k; 
 // 原始链表正好可以由 K 分位 N 组，可直接处理 
 if (offsetIndex == 0) { 
 return reverseKGroup(head, k); 
 } 
 
 // 定义并找到 prev 和 offset 
 ListNode prev = head, offset = head; 
 while (offsetIndex > 0) { 
 prev = offset; 
 offset = offset.next; 
 offsetIndex--; 
 } 
 
 // 将 offset 结点子链表进行翻转，再拼接回主链表 
 prev.next = reverseKGroup(offset, k); 
 return head;
}

注意当链表长度正好可以用 K 分位 N 组时，我们直接处理，否者才需要后续复杂的逻辑。

代码的注释足够清晰了，在脑子里过一遍代码的执行流程应该能明白，为了帮助大家理解，我又画了个示意图。

假设以 head 为头结点的链表长度是 10，K 为 4，那么计算下来 offset Index 就是 2。