正文

字节跳动笔试题:链表反转(代码片段)

wyq178  wyq178  2023-03-21  424

关键词：

前言从业快4年,最近愈发感觉到算法的重要性.作为一名后端开发,在实际工作中,算法的应用其实是十分多的，比如我们熟悉的LinkedList、jdk的底层排序，算法的重要性大家都有目共睹，也基本成了入职大厂不可或缺的基本能力。最近就听群里的伙伴说面试字节跳动的时候要求现场写出以k个为一组反转链表，如果不做准备，之前没有一点了解，看到这种题目，很容易懵逼，那么肯定就必挂无疑了。

算法的种类很多,数组、链表、二叉树、动态规划、贪心、回溯等(越来越感觉到自己的脑壳在主键变亮堂了，头发在渐渐稀疏了- 。-).本篇博客就来探讨一下在面试中，特别常见的关于链表几道题：

一：从反转一个链表说起

二：以K个为一组翻转链表

三：翻转m到n区间的链表

四：总结

一：从反转一个链表说起

技术图片

1.1：思路

链表作为一种以指针联系的数据结构，无法像数组一样进行某个元素的随机访问。在解决链表的问题上,我们唯一的法宝就是指针，通过定义不同的指针互相指引来改变聊表的顺序来解决棘手的问题。仔细分析这道题，发现链表的反转本质上将下一个节点的指针指向前一个指针,按照从局部到整体的解决思路。我们可以将这个问题化成下一个节点指向前一个节点的过程，只要依次循环这个过程，就可以得到最终的结果：

技术图片

1.2：代码

 /**
     * 从头开始翻转链表
     *
     * @param node
     * @return
     */
    public ListNode reverse(ListNode node) 

        ListNode pre = null;
        ListNode curr = node;
        while (curr != null) 
            ListNode next = curr.next;
            //将指针指向前面的一个节点
            curr.next = pre;
            pre = curr;
            curr = next;
        
        return pre;

1.3：测试

public static void main(String[] args) 

        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);

        final ListNode reverse = new ReverseNode().reverse(node);
        System.out.println(reverse);

技术图片

二：以K个为一组翻转链表

技术图片

2.1：思路

在这个问题中，其实可以大致的把链表分为三组:未翻转区,待翻转区,已翻转区,然后通过定义4个指针来切断我们需要翻转的链表,为什么需要4个指针，往下看你就可以明白了。

这4个指针分别是:

prev:前置指针,作用是定位将要翻转的前一个位置

next:后置指针,作用是定位要翻转结束的后一个位置

start:待翻转的开始指针,定位翻转的链表的开始位置

end:翻转结束的指针,定位翻转链表的结束位置

2.2：画图表示

技术图片

2.3:代码

 public ListNode reverseGroup(ListNode head, int k) 

        //创建一个预设节点
        ListNode dump = new ListNode(0);

        dump.next = head;
        //pre节点
        ListNode pre = dump;
        //end节点
        ListNode end = dump;

        while (end != null) 
            //确定需要反转区间的尾节点
            for (int i = 0; i < k; i++) 
                //移动end指针
                end = end.next;
                if (end.next == null) 
                    return dump.next;
                
            
            //确定需要翻转的子区间的头结点
            ListNode start = pre.next;
            //断开子区间和后面的连接
            ListNode next = end.next;
            end.next = null;
            //翻转start到end区间
            pre.next = reverse(start);
            start.next = next;
            pre = start;
            end = start;
        
        return dump.next;
    

    /**
     * 从头开始翻转链表
     *
     * @param node
     * @return
     */
    public ListNode reverse(ListNode node) 

        ListNode pre = null;
        ListNode curr = node;
        while (curr != null) 
            ListNode next = curr.next;
            //将指针指向前面的一个节点
            curr.next = pre;
            pre = curr;
            curr = next;
        
        return pre;

2.4：测试类

public static void main(String[] args) 

        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);
        node.next.next.next.next.next = new ListNode(6);
        node.next.next.next.next.next.next = new ListNode(7);
        node.next.next.next.next.next.next.next = new ListNode(8);

        ListNode resultNode = new ReverGroup2().reverseGroup(listNode,3);
        System.out.println(resultNode);

技术图片

三：翻转m到n区间的链表

技术图片

3.1：思路

借鉴于第一题的思路,同样需要定义4个指针，分别是prev,next,start,end和上面的含义基本相似。不同的是这次限定了翻转的区间，所以本次需要按照以下步骤：

①定义pre指针,走m-1步,来到待翻转链表的区间的前一个节点

②定义end指针,值和pre相同,然后走n-m+1个步骤来到待翻转链表的结尾节点

③定义start节点,指向pre的next,这里的目的是为了我们需要将m-n区间范围的链表进行截取，之后需要拼凑，因此需要记录截取前的头指针位置

④定义next节点,指向end节点的下一个节点,作用和③的功能类似,记录截取后的尾结点的指针位置

3.2：画图

画图来表示一下：

技术图片

3.3：代码

 /**
     * 使用 4 个指针变量的解法
     * @param head
     * @param m
     * @param n
     * @return
     */
    public ListNode reverseBetween(ListNode head, int m, int n) 
        // 因为有头结点有可能发生变化，使用虚拟头结点可以避免复杂的分类讨论
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode prev = dummyNode;
        // 第 1 步：从虚拟头结点走 m - 1 步，来到 m 结点的前一个结点
        // 建议写在 for 循环里，语义清晰
        for (int i = 0; i < m - 1; i++) 
            prev = prev.next;
        

        // 第 2 步：从 prev 再走 n - m + 1 步，来到 n 结点
        ListNode end = prev;
        for (int i = 0; i < n - m + 1; i++) 
            end = end.next;
        

        // 第 3 步：切断出一个子链表（截取链表）
        ListNode start = prev.next;
        ListNode next = end.next;

        prev.next = null;
        end.next = null;

        // 第 4 步：反转子链表
        reverse(start);

        // 第 5 步：接回到原来的链表中
        prev.next = end;
        start.next = next;
        return dummyNode.next;

    

/**
 * 翻转链表
 * @param head
 */
private void reverse(ListNode head) 
        // 也可以使用递归反转一个链表
        ListNode pre = null;
        ListNode cur = head;
        // 在循环开始之前声明，可以避免在循环中反复声明新变量
        ListNode next;

        while (cur != null) 
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;

3.4：测试用例

public static void main(String[] args) 

        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);
        node.next.next.next.next.next = new ListNode(6);
        node.next.next.next.next.next.next = new ListNode(7);

        ListNode resvers = new ReverseListNodeBetween().reverseBetween(node,3,5);

        System.out.println(resvers);

输出结果：

技术图片

四：总结

链表作为经典的数据结构,本篇博客从反转链表说起,然后分析了每k个一组翻转和从m到n之间的翻转，都是反转的变形题目,难度也依次增大.其中可以看到解决链表的反转问题本质上的最行之有效的方法就是通过定义不同作用的指针，来改变指针值从而改变链表的整个顺序。对于这种思想的理解，也有助于我们理解链表这种数据结构。加油~

最后: 如果对学习java有兴趣可以加入群:618626589,本群旨在打造无培训广告、无闲聊扯皮、无注水斗图的纯技术交流群，群里每天会分享有价值的问题和学习资料,欢迎各位随时加入～

92.反转链表ii-字节跳动高频题(代码片段)

一、题目描述给你单链表的头指针head和两个整数left和right，其中left<=right。请你反转从位置left到位置right的链表节点，返回反转后的链表。示例1：输入：head=[1,2,3,4,5],left=2,right=4输出：[1,4,3,2,5]示... 查看详情

[11道链表经典笔试题]优化的算法思想：反转链表链表相交快慢指针(代码片段)

1.删除链表中等于给定值val的所有节点AC代码/***Definitionforsingly-linkedlist.*structListNode*intval;*structListNode*next;*;*/structListNode*removeElements(structListNode*head,intval)structListNode*prev=NULL,*cur=head;w 查看详情

字节跳动2017客户端工程师实习生笔试题-第四题(代码片段)

链表后半部分反转（2016亚信实习生笔试题）

题目（2016亚信实习生笔试题）：将链表后半部分反转，编写功能函数。函数头类似于本代码中reList()。只记得一个大概了，具体规则在代码注释中提到了。#defineNULL0#include<stdio.h>typedefstructLNodecharvalue;structLN... 查看详情

字节跳动算法整理(代码片段)

目录无重复字符的最长子串最长公共前缀*简化路径复原IP三数之和岛屿的最大面积搜索旋转排序数组朋友圈接雨水反转链表两数相加合并K个升序链表买卖股票的最佳时机买卖股票的最佳时机II最大子序和最小栈LRU缓存机制x的平... 查看详情

字节跳动（今日头条）的题目真的难吗？

...都努力精进，并努力分享的主儿。今天给聊得话题是关于字节跳动笔试题难度的。在各种交流群了，总是能看到大家在说字节跳动的题目好难呀，4个编程题没有一个题AC。天天觉得大家好难呀，所以找了一些==字节跳动==关于自... 查看详情

字节跳动+百度+阿里巴巴高频面试题之链表专题(代码片段)

...巴巴二面原题）2、判断单链表是否是回文结构。（2019年字节跳动二面原题）3、删除一个有序单链表中的重复节点。（2019年字节跳动二面原题）4、复杂链表的复制。（2020年百度二面原题）1、逆置一个单链表。OJ链接：https://leet... 查看详情

字节跳动（今日头条）的题目真的难吗？

字节笔试题（含答案）(代码片段)

个人博客欢迎访问总结不易，如果对你有帮助，请点赞关注支持一下微信搜索程序dunk，关注公众号，获取博主的数据结构与算法的代码笔记目录2019春招研发部分编程题万万没想到之聪明的编辑(AC)思路代码万万没... 查看详情

每日一题|曾被反转链表支配的恐惧(代码片段)

...eetCode的每日一题刚好是反转链表，这道去年年初面试字节跳动挂掉的算法题，趁这个机会把之前算法的记忆捡回来。Date:2021-03-21Week121、反转链表II难度：Medium题目描述给你单链表的头指针head和两个整数left和right 查看详情

每日一题|曾被反转链表支配的恐惧(代码片段)

字节跳动技术训练营—后端开发专场机试题解(代码片段)

目录1、扑克牌重新洗牌2、二叉树的路径总和3、剧本杀但是由于牛客的笔试环境不能截图，离开三次就算作弊，所以我只能靠回忆写一写题目。1、扑克牌重新洗牌大概意思是说有一副扑克牌，需要重新洗牌。黑桃、... 查看详情

常见的链表翻转，字节跳动加了个条件，面试者高呼：我太难了！(代码片段)

一.序我又来讲链表题了，这道题据说是来自字节跳动的面试题。为什么说是「据说」呢？因为我也是看来的，觉得题目还是挺有意思，但是原作者给出的方案，我想了想觉得还有优化空间，就单独拿出来... 查看详情

字节跳动高频算法题top100

题目出现次数3.无重复字符的最长子串10625.K个一组翻转链表84206.反转链表83215.数组中的第K个最大元素81146.LRU缓存机制68103.二叉树的锯齿形层次遍历6415.三数之和62121.买卖股票的最佳时机61160.相交链表581.两数之和48236.二叉树的最... 查看详情

c++笔试题——每天学一点，天天都进步(代码片段)

...是多少？()A.24B.28C.16D.18答案解析64位系统下指针为8个字节，a1占4字节，a2两字节，由于a3占4字节，a2需要补齐2个字节࿰ 查看详情

百度笔试题简述大小端字节序的概念并写一个小程序检测当前机器的大小端字节序(代码片段)

...出相应的讲解，希望对你们有所帮助~题目：请简述大端字节序和小端字节序的概念，设计一个小程序来判断当前机器的字节序。（10分）标准答案如下：(1)Littleendian：将低序字节存储在起始地址Bigendian：将高序字节存储在起始地... 查看详情

百度笔试题简述大小端字节序的概念并写一个小程序检测当前机器的大小端字节序(代码片段)

数据挖掘顺丰公司数据挖掘笔试题(代码片段)

【数据挖掘】顺丰公司数据挖掘笔试题1、二叉排序树的链表节点定义如下：typedefstructBiTnodeintkey_value;structBiTnode*L,*R;/节点的左、右树指针/请补充完整查找键值key的函数。（D）BSTreelookup_key(BSTreeroot,intkey)if()returnNULL;elsei... 查看详情