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

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


🌏引言

单链表的操作算法是笔试面试中较为常见的题目。

本文将着重介绍平时面试中常见的关于链表的应用题目,马上要进行秋招了。希望对你们有帮助 _😀

🍀相交链表

🎄题目描述

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

图示两个链表在节点 c1 开始相交:

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

/**
 * 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) {
    }
}

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

🎍示例

🚩示例一

🚩示例二

🚩示例三

🎋解法思路

我们发现,两个链表如果相交

那我们就可以让长链表先走等于它们之间差值的步数

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

🚩相关变量的建立

我们将

  • 长的链表用指针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) {
    }
}

🎍 示例

🚩示例一

🚩示例二

🚩示例三

🎋思路解析:

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

比如环形操场上跑步:

🌴扩展问题

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

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

🌳完整代码:

/**
 * 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 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

🎍示例

🚩示例一

🚩示例二

🚩示例三

🎋思路解析:

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

图解如下:

🌳完整代码

/**
 * 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;
    }
}

⭕总结

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

相关文章
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
39 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
35 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
2月前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
26 1
|
3月前
|
存储 Java
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
2月前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
|
2月前
|
存储
数据结构2——单链表
数据结构2——单链表
34 1
|
2月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
2月前
|
存储
数据结构(单链表)
数据结构(单链表)
18 0
|
2月前
|
存储
数据结构--单链表
数据结构--单链表
|
2月前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(二)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)