罕见的链表翻转，字节跳动加了个前提，口试者高呼「我太难了」| 图解算法

2019-11-18杂谈搜奇网45°c

A⁺ A^-

本文首发自民众号「承香墨影（ID：cxmyDev）」，迎接关注。

一. 序

我又来讲链表题了，这道题听说是来自字节跳动的口试题。

为何说是「听说」呢？由于我也是看来的，以为题目照样挺有意义，然则原作者给出的计划，我想了想以为另有优化空间，就零丁拿出来讲讲。

就像本文的题目说的，这是一道关于链表翻转的题。链表的翻转，之前的文章也讲了许多，比方：链表翻转、链表两两翻转、K 个一组翻转链表。这些实在都是 leetcode 上的规范题，然则一般企业给出的口试题，多数会做一些变种，也就是加一些特别的前提。

比方本日要讲的这道题。

给订单链表的头结点 head，完成一个调解链表的函数，从链表尾部最先，以 K 个结点为一组举行逆序翻转，头部盈余结点不足一组时，不须要翻转。（不能运用行列或许栈作为辅佐）

仔细读题，像不像我们之前讲到的 leetcode 第 25 题：K 个一组翻转链表。

leetcode-25 是重新结点最先，以 K 个结点一组举行翻转。而字节跳动这道题，是从尾结点最先。

只是多了一个从尾结点最先分组翻转的前提，这道题的难度就增添了。

二. K个一组翻转链表（头条版）

2.1 其他人的解题思绪

前面也说到，这道题是我看来的，当时是以一篇文章的情势宣布出来。

文章我就不发了，不过先相识一下他的解题思绪，有助于我们思索。

他的思绪很清楚，虽然这道题他不会解，然则 leetcode-25 这个规范的以 K 个一组翻转链表的题他很熟习。

那末能够先将原始链表，举行一次「链表翻转」，再举行「K 个一组翻转链表」，末了再做一次「链表翻转」复原链表，就得出了须要的效果。

ListNode revserseKGroupPlus(ListNode head, int k) {
  // 翻转链表
  head = reverseList(head);
  // K 个一组翻转链表
  head = reverseKGroup(head, k);
  // 翻转链表
  head = reverseList(head);
  return head;
}

把一个不熟习的题目，经由简朴的转换，变成熟习的题目举行处置惩罚，这类思绪是没有错的。

然则呢，有个题目--

在口试的场景中，一般来讲，口试官的程度会高于口试者，那末我们能够简朴的邃晓，口试就是一个不停受挫的历程，这个历程总会被问到我们学问的边境才会住手。

口试题只是出发点，口试历程当中深挖的哪些题目，才是触摸到我们谈薪资源的中心。固然这扯远了，继承回到本文的内容。

此时就算口试者就地写出相识题代码，也逃不开一个典范题目。

口试官：「另有更优的计划吗？」

那末这道题，有无更优的计划？答案固然是有的。

2.2 更优一点的计划

将链表先翻转后处置惩罚，再翻转归去，如许并不文雅，实在只需一次以 K 个一组翻转链表就能够。

再回想一下 leetcode 第 25 题，它和这道题的差别，重要来自于，对不足一组的链表结点的处置惩罚。leetcode-25 是重新结点最先处置惩罚，所以多出来的结点会在尾部，而字节跳动这道题则恰好相反，余下的结点会在头部。

然则它们同时也有一种特别情况，就是 K 个一组举行分组时，这里的 K 恰好能够完全的分组，一个不多，一个不少的分红 N 组。

当链表结点数目恰好为 K * N 时，那末又回到了我们熟习的 leetcode-25 题了。

假如我们先将原始结点举行处置惩罚，找出它恰好能够整除 K 的肇端结点 offset，将这个肇端结点 offset 的子链表，再举行 K 个一组举行翻转链表，末了把它拼接回原始链表，就完成了这道题。

这个历程，须要分外定义两个结点，第一个满足 K 个分组前提的 offset 结点，以及 offset 的先驱结点 prev 结点，prev 结点重如果用来拼接翻转后的两个链表，让其不会涌现链表断裂的题目。

它们的关联以下：

这个中还涉及到一些简朴的链表运算，比方求链表的长度，这里就不睁开说了，直接上中心代码，逻辑都在解释里，我们先定义一个 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。

找到 prev 和 offset 结点后，就能够将以 offset 结点为头结点的子链表，举行 K 个一组翻转链表的操作了。

此时，head 结点为肇端的链表，就是我们盘算后的效果。

2.3 再补一些分外的代码

这道题，还涉及到许多其他的小算法，自身 leetcode-25 就已被定级为「难题」，字节跳动在这道题的基础上，又增添了难度。

为了保证解题的完全，这里再补充一些相干代码。

1. 盘算链表长度

private int linkedLength(ListNode head) {
    int count = 0;
    while (head != null) {
        count++;
        head = head.next;
    }
    return count;
}

没什么好说的，一个 while 轮回搞定。

2. 以 K 个一组翻转链表

这道题在之前的文章中细致讲解了，这里直接贴代码了。

public ListNode reverseKGroup(ListNode head, int k) {
    // 增添假造头结点
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    // 定义 prev 和 end 结点
    ListNode prev = dummy;
    ListNode end = dummy;

    while(end.next != null) {
      // 以 k 个结点为前提，分组子链表
      for (int i = 0; i < k && end != null; i++)
        end = end.next;
      // 不足 K 个时不处置惩罚
      if (end == null)
        break;
      // 处置惩罚子链表
      ListNode start = prev.next;
      ListNode next = end.next;
      end.next = null;
      // 翻转子链表
      prev.next = reverseList(start);
      // 将子连表前后串起来
      start.next = next;
      prev = start;
      end = prev;
    }
    return dummy.next;
}

// 递归完成单链表翻转
private ListNode reverseList(ListNode head) {
    if (head == null || head.next == null)
      return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

关于 leetcode-25 这道题，还不太相识的能够看看之前的文章《K 个一组翻转链表》。