【数据结构】 单链表面试题讲解->壹

这篇具有很好参考价值的文章主要介绍了【数据结构】 单链表面试题讲解->壹。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

引言

单链表的操作算法是笔试面试中较为常见的题目。
本文将着重介绍平时面试中常见的关于链表的应用题目,马上要进行秋招了。希望对你们有帮助 _😀
【数据结构】 单链表面试题讲解->壹,数据结构,数据结构,java,算法,面试题

反转单链表

题目描述

给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。

数据范围: 0≤n≤1000

要求:空间复杂度 O(1) ,时间复杂度 O(n) 。

如当输入链表{1,2,3}时,
经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。
以上转换过程如下图所示:
【数据结构】 单链表面试题讲解->壹,数据结构,数据结构,java,算法,面试题

示例:

【数据结构】 单链表面试题讲解->壹,数据结构,数据结构,java,算法,面试题

题解思路

(1)定义两个指针: pser 和 sur ;sur 在前 pser 在后。
【数据结构】 单链表面试题讲解->壹,数据结构,数据结构,java,算法,面试题
(2)sur用于遍历,pser用于交换位置,并插入到头节点前面

(3)将head里面的next置为null

(4)每一次插入顺序为将sur的位置付给pser,然后sur向前走一步,令pser里的next设为head;这时候pser为头节点,我们再将pser赋给head作为新的头节点。每循环一次头节点向前走一步
【数据结构】 单链表面试题讲解->壹,数据结构,数据结构,java,算法,面试题

(5)循环上述过程,直至 sur 到达链表尾部
【数据结构】 单链表面试题讲解->壹,数据结构,数据结构,java,算法,面试题

代码实现:

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // write code here

        if (head == null || head.next == null) {
            return head;
        }

        ListNode sur = head.next;
        ListNode pser = head;
        head.next = null;
        while (sur != null) {
            pser = sur;
            sur = sur.next;
            pser.next = head;
            head = pser;
        }
        return head;
    }
}

移除链表元素

题目描述:

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

示例

【数据结构】 单链表面试题讲解->壹,数据结构,数据结构,java,算法,面试题

思路解析:

我们依旧需要对该单链表进行判断,如果为空,就直接返回

由于我们需要删除很多个这样的节点,但是我们的单链表却是单向的,按照上面的写法,我们则需要遍历很多次单链表,大大的增加了复杂度,我们为了降低时间复杂度,使它降为O(N);

我们设两个遍历节点,进行遍历,一个在前为cur,一个在后prev
【数据结构】 单链表面试题讲解->壹,数据结构,数据结构,java,算法,面试题
前面的cur负责进行遍历删除,后面的prev负责跟在cur后面记录cur的上一节点

当cur下一节点不是我们所要删除的元素时,这时候我们将prev变为我们当前节点的cur,而cur变为当前节点的next

【数据结构】 单链表面试题讲解->壹,数据结构,数据结构,java,算法,面试题
当前的删除方法只能删除第一个节点以后的元素,所以我们还需要处理第一个元素是我们所需要删除的情况。

代码实现如下

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) {
            return null;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if(cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.val == val) {
            head = head.next;
        }
        return head;
    }
}

链表的中间结点

题目描述:

给你单链表的头结点 head ,请你找出并返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

示例:

【数据结构】 单链表面试题讲解->壹,数据结构,数据结构,java,算法,面试题

思路解析

我们依旧两个定义两个指针,一个一次性走两步,一个一次性走一步

当快的指针到达终点时,慢的指针所☞指位置就是我们所需要的中间位置

就像大人与小孩子一起走路,大人的速度是小孩子的两倍
【数据结构】 单链表面试题讲解->壹,数据结构,数据结构,java,算法,面试题
大人到达终点时,小孩子才走到一半!

代码实现如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //1、找中间节点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

注意:fast != null与fast.next != null不可以调换

链表中倒数第k个结点

题目描述

输入一个链表,输出该链表中倒数第k个结点。

示例

输入:
1,{1,2,3,4,5}
返回值:
{5}

思路解析:

依旧是两个指针,分别为fast和slow,fast先出发,fast出发k-1步后,slow出发,中间保持k-1个节点的距离,fast所指向下一节点为null时结束

【数据结构】 单链表面试题讲解->壹,数据结构,数据结构,java,算法,面试题

代码实现如下:

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        if (k <= 0 || head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        //1. fast走k-1步
        while (k - 1 != 0) {
            fast = fast.next;
            if (fast == null) {
                return null;
            }
            k--;
        }
        //2、3、
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

总结

关于《【数据结构】 单链表面试题讲解》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!文章来源地址https://www.toymoban.com/news/detail-667153.html

到了这里,关于【数据结构】 单链表面试题讲解->壹的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构练习】链表面试题锦集一

    目录 前言: 1. 删除链表中所有值为key的节点  方法一:正常删除,头结点另外讨论  方法二:虚拟头结点法  方法三:递归 2.反转链表  方法一:双指针迭代   方法二:递归法 3.链表的中间结点   方法:快慢指针法 4. 链表中倒数第k个结点  方法:快慢指针方法 5.合并两个

    2024年02月11日
    浏览(36)
  • 【数据结构】单链表 | 详细讲解

    无须为了表示中间的元素之间的逻辑关系而增加额外的存储空间; 因为以数组形式存储,可以快速地存取表中任一位置的元素。 插入和删除操作需要移动大量元素,时间复杂度为O(N); 当线性表长度变化较大时,难以确定存储空间的容量; 造成存储空间的“碎片”。 其实顺

    2024年02月05日
    浏览(45)
  • 【数据结构】线性表之单链表(讲解实现——带动图理解)

    单链表的优点 1.头部和中间插入或删除数据效率高,无需挪动。 2.按照需求申请释放空间,无需担心空间不够用。 单链表的缺点 1.不可以进行下标随机访问。 2.复杂度是O(n) 3.反向遍历困难 单链表是线性表的一种,单链表是链式存储的线性表,不同于单链表, 链表在内存空间

    2024年02月06日
    浏览(45)
  • 单链表面试题思路分享二

    我们紧接上文单链表面试题分享一来看看本章我要分享的题目,共四个题目,我还是把它在力扣或者牛客网的链接交给大家: 1.合并两个有序链表 力扣21题----- 2.链表的分割 牛客网cc149----- 3.链表的回文结构 力扣234题----- 4.链表相交 力扣160题, 本次分享还是和之前一样,代码用c语言

    2023年04月23日
    浏览(50)
  • 带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

    🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨ 🐻推荐专栏: 🍔🍟🌯 C语言进阶 🔑个人信条: 🌵知行合一 🍉本篇简介::讲解数据结构中链表的知识,;链表的分类,c语言实现单链表常见接口等. 金句分享: ✨山不向我走来,我便向山走去.✨ 顺序表 缺点: 中间/头部的插入删除,时间复杂

    2024年02月03日
    浏览(33)
  • Java 数据结构篇-实现单链表核心API

    🔥博客主页:  小扳_-CSDN博客 ❤感谢大家点赞👍收藏⭐评论✍     文章目录         1.0 单链表的说明         2.0 单链表的创建         2.1 单链表 - 头插节点         2.2 单链表 - 遍历         2.2.1 使用简单的 for/while 循环         2.2.2 实现 forEach 方法         2.2.

    2024年02月05日
    浏览(47)
  • 数据结构常见面试题及详细java示例

    下面是一些常见的数据结构面试题以及使用Java实现的解决方案。 1、如何在给定数组中找到重复的元素?         使用HashSet是一个常见的解决方法。 2、链表反转         反转链表是最常见的数据结构问题之一。以下是用Java实现的一个例子。 3、二叉树的深度     

    2024年04月12日
    浏览(37)
  • Java------数据结构之栈与队列(简单讲解)

    本篇碎碎念 :时隔n个月,继续写博客,假期落下的进度,在开学后努力追赶, 假期不努力,开学徒伤悲啊,此时此刻真想对自己说一句,活该啊~~~~ 欠下的链表练习题讲解会在下次更新~~~~ 今日份励志文案:  万物皆有裂痕,那是光照进来的地方 栈:一种特殊的线性表,其只允

    2024年04月14日
    浏览(57)
  • java数据结构(哈希表—HashMap)含LeetCode例题讲解

      目录 1、HashMap的基本方法 1.1、基础方法(增删改查) 1.2、其他方法  2、HashMap的相关例题 2.1、题目介绍 2.2、解题 2.2.1、解题思路 2.2.2、解题图解 2.3、解题代码 HashMap 是一个散列表,它存储的内容是键值(key-value)映射。 HashMap 的 key 与 value 类型可以相同也可以不同,根据定

    2024年02月05日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包