hi,你好!欢迎访问本站!登录
本站由网站地图腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - 教程 - 杂谈 - 正文 君子好学,自强不息!

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

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 个一组翻转链表》。

三. 小结时候

以上就是我解这道题的思绪,能够不是最高效的,但也算是比较清楚。

在口试历程当中,链表相干的题目能够说是高频题。虽然企业在出题时,为了增添难度也会做一些变种,然则作为口试者,无论如何都避不开多练多写多想。

你有更好的计划吗?你在口试中有遇到什么奇葩的算法题吗?迎接在留言区议论。

本文对你有协助吗?留言、转发、珍藏是最大的支撑,感谢!

民众号背景复兴生长『生长』,将会获得我预备的进修材料,也能复兴『加群』,一同进修提高。

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

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

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
未定义标签

本文来源:搜奇网

本文地址:https://www.sou7.cn/282320.html

关注我们:微信搜索“搜奇网”添加我为好友

版权声明: 本文仅代表作者个人观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。请记住本站网址https://www.sou7.cn/搜奇网。

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>