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

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


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

🍀相交链表

🎄题目描述

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

图示两个链表在节点 c1 开始相交:
【数据结构】 单链表面试题讲解->叁,数据结构,数据结构,java,相交链表,开发语言,面试,环形链表

题目数据 保证 整个链式结构中不存在环。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  
    }
}

注意,函数返回结果后,链表必须 保持其原始结构 。

🎍示例

🚩示例一

【数据结构】 单链表面试题讲解->叁,数据结构,数据结构,java,相交链表,开发语言,面试,环形链表

🚩示例二

【数据结构】 单链表面试题讲解->叁,数据结构,数据结构,java,相交链表,开发语言,面试,环形链表

🚩示例三

【数据结构】 单链表面试题讲解->叁,数据结构,数据结构,java,相交链表,开发语言,面试,环形链表

🎋解法思路

我们发现,两个链表如果相交
【数据结构】 单链表面试题讲解->叁,数据结构,数据结构,java,相交链表,开发语言,面试,环形链表
那我们就可以让长链表先走等于它们之间差值的步数

然后再同时出发,当两指针相等时,返回该节点

🚩相关变量的建立

我们将

  • 长的链表用指针log表示
  • 短的链表用指针sot表示
  • 链表headA的长度用lenA表示
  • 链表headB的长度用lenB表示
  • len为lenA与LenB的差值

🚩求两链表的长度与差值

直接遍历,然后相减即可

	while(log != null) {
            log = log.next;
            lenA ++;
        }
        while(sot != null) {
            sot = sot.next;
            lenB ++;
        }
        int len = lenA - lenB;

🚩确定长短链表

因为我们一开始并不知道两个链表谁长谁短,所以博主再赋初始值时,给log赋值的是headA;给sot赋值的是sot;

ListNode log = headA;
ListNode sot = headB;

判断len:

  • len<0说明headB长度大于headA
  • 交换log与sot,len值重置;
log = headB;
sot = headA;
len = lenB - lenA;

注意:如果len大于0,因为我们的log与sot的值已经改变,所以我们需要重新赋值

代码实现如下:

 		if(len < 0) {
            len = lenB - lenA;
            log = headB;
            sot = headA;
        } else {
            log = headA;
            sot = headB;
        }

🚩长链表先走len步

 while(len != 0) {
            log = log.next;
            len--;
        }

🚩同时走,找交点

		while(log != sot) {
            log = log.next;
            sot = sot.next;
        }

🌳完整代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode log = headA;
        ListNode sot = headB;
        int lenA = 0;
        int lenB = 0;
        while(log != null) {
            log = log.next;
            lenA ++;
        }
        while(sot != null) {
            sot = sot.next;
            lenB ++;
        }
        int len = lenA - lenB;
        if(len < 0) {
            len = lenB - lenA;
            log = headB;
            sot = headA;
        } else {
            log = headA;
            sot = headB;
        }
        while(len != 0) {
            log = log.next;
            len--;
        }
        while(log != sot) {
            log = log.next;
            sot = sot.next;
        }
        return log; 
    }
}

🍀环形链表

🎄题目描述:

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
       
    }
}

🎍 示例

🚩示例一

【数据结构】 单链表面试题讲解->叁,数据结构,数据结构,java,相交链表,开发语言,面试,环形链表

🚩示例二

【数据结构】 单链表面试题讲解->叁,数据结构,数据结构,java,相交链表,开发语言,面试,环形链表

🚩示例三

【数据结构】 单链表面试题讲解->叁,数据结构,数据结构,java,相交链表,开发语言,面试,环形链表

🎋思路解析:

快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从链表起始位置开始运行,如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾。

比如环形操场上跑步:
【数据结构】 单链表面试题讲解->叁,数据结构,数据结构,java,相交链表,开发语言,面试,环形链表

🌴扩展问题

  • 为什么快指针每次走两步,慢指针走一步可以? 假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。当慢指针刚进环时,可能就和快指针相遇了,最差情况下两个指针之间的距离刚好就是环的长度。此时,两个指针每移动一次,之间的距离就缩小一步,不会出现每次刚好是套圈的情况,因此:在慢指针走到一圈之前,快指针肯定是可以追上慢指 针的,即相遇。

快指针一次走3步,走4步,…n步行吗?

  • 【数据结构】 单链表面试题讲解->叁,数据结构,数据结构,java,相交链表,开发语言,面试,环形链表

🌳完整代码:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }
}

🍀环形链表||

🎄题目描述:

给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

🎍示例

🚩示例一

【数据结构】 单链表面试题讲解->叁,数据结构,数据结构,java,相交链表,开发语言,面试,环形链表

🚩示例二

【数据结构】 单链表面试题讲解->叁,数据结构,数据结构,java,相交链表,开发语言,面试,环形链表

🚩示例三

【数据结构】 单链表面试题讲解->叁,数据结构,数据结构,java,相交链表,开发语言,面试,环形链表

🎋思路解析:

让一个指针从链表起始位置开始遍历链表,同时让一个指针从判环时相遇点的位置开始绕环运行,两个指针都是每次均走一步,最终肯定会在入口点的位置相遇。

图解如下:
【数据结构】 单链表面试题讲解->叁,数据结构,数据结构,java,相交链表,开发语言,面试,环形链表

🌳完整代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode cur = head;
        int count = 0;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                count = 1;
                break;
            }
        }
        if(count == 0) {
            return null;
        }
    
        while(cur != slow) {
            slow = slow.next;
            cur = cur.next;
        }
        return cur;
    }
}

⭕总结

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

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

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

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

相关文章

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

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

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

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

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

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

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

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

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

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

    2024年02月03日
    浏览(35)
  • 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日
    浏览(51)
  • 数据结构常见面试题及详细java示例

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

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

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

    2024年04月14日
    浏览(58)
  • 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日
    浏览(52)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包