图解:K 个一组翻转链表 | LeetCode 级别:困难

8,325 阅读4分钟

本文首发自公众号:承香墨影(ID:cxmyDev),欢迎关注。

一. 序

链表作为一种基本的数据结构,本身理解起来很简单。它通过指针,将一组零散的内存空间(结点),串联起来,组成一个数据结构。

在面试的算法题中,经常会碰到链表相关的面试题。虽然链表的结构比较好理解,但是链表的题还是比较考教代码能力的。一些单链表的题,指针指来指去,很容易就把结点的 next 指针弄丢了,造成链表断裂。

链表翻转是一个面试中经常会碰到的题,在之前的文章中,也聊过单链表翻转链表双双翻转,今天再来聊聊它们的「升级版」,以 K 个为一组,翻转链表,同时这也是 LeetCode 的第 25 题。

二. K 个一组翻转链表

以 K 个结点为一组,将给定的单链表进行翻转。有点类似之前的链表两两翻转,只是那时的 K = 2。而在这道题中,K 变成一个外部传入的正整数,它是一个可变的值,并且小于或者等于链表的长度。

这道算法题,会用到之前的知识,既然 K 是可变的,我们无法估计 K 的大小,但是我们可以将原始链表,以 K 个结点为一组,执行单链表翻转的逻辑。

这就要用到之前《单链表翻转》的技巧了,不了解的建议先读读之前的文章。

既然需要将原始链表先以 K 个结点分组,再依次执行单链表翻转,在每组字链表翻转之后,还需要将它们再串起来,否者链表不就断裂了么。

这就需要使用两个变量 prev 和 end,分别记录子链表的前驱结点,以及子链表的尾结点。有了 end 这个子链表的尾结点,就可以很容易通过 end.next 拿到下一个子链表的头结点。

依据这几个结点,就可以完成子链表的翻转,以及保证在子链表翻转后依然可以串起来。

另外有一个特殊处理的地方,当原始链表以 K 个结点为一组分组时,末尾不满一组的子链表,保持原样不进行翻转。

参考链表两两翻转的思路,为了保证我们的代码逻辑统一,我们增加一个虚拟的头结点 dummy,来方便我们编写代码。

直接上代码,细节都在注释里。

class Solution {
  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;
  }
}

这里单链表的翻转,使用了递归,一般 K 值都不会太大,所以用递归没问题,当然你也可以换成循环实现。对细节不了解的,可以参见《单链表翻转》。

三. 小结时刻

到这里单链表,按 K 分组翻转的具体思路和代码,就介绍清楚了。我这种处理方式可能不是最高效的,但是应该是比较清晰的。

另外在实际面试中,其实很多场景下,都不会直接出 leetcode 上的算法题,都会稍微变种一下,但是大家要学会将复杂问题,转化为简单问题来解决。

到这里,链表翻转的基础题,基本上就说清楚了,包含三个篇文章:

今天就到这里,有任何问题欢迎留言讨论。

本文对你有帮助吗?留言、转发、收藏是最大的支持,谢谢!


公众号后台回复成长『成长』,将会得到我准备的学习资料。