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

Bertha 。 2024-04-17 10:43 85阅读 0赞

#### 文章目录 ####

*  ?\[相交链表\](https://leetcode.cn/problems/intersection-of-two-linked-lists/description/)
 *   *  ?题目描述
     *  ?示例
     *   *  ?示例一
         *  ?示例二
         *  ?示例三
     *  ?解法思路
     *   *  ?相关变量的建立
         *  ?求两链表的长度与差值
         *  ?确定长短链表
         *  ?长链表先走len步
         *  ?同时走，找交点
     *  ?完整代码
 *  ?\[环形链表\](https://leetcode.cn/problems/linked-list-cycle/description/)
 *   *  ?题目描述：
     *  ? 示例
     *   *  ?示例一
         *  ?示例二
         *  ?示例三
     *  ?思路解析：
     *  ?扩展问题
     *  ?完整代码：
 *  ?\[环形链表||\](https://leetcode.cn/problems/linked-list-cycle-ii/description/)
 *   *  ?题目描述：
     *  ?示例
     *   *  ?示例一
         *  ?示例二
         *  ?示例三
     *  ?思路解析：
     *  ?完整代码
 *  ⭕总结

?引言  
单链表的操作算法是笔试面试中较为常见的题目。  
本文将着重介绍平时面试中常见的关于链表的应用题目，马上要进行秋招了。希望对你们有帮助 \_?  
![在这里插入图片描述][94b094fa0d0f42bcac0a437a41e1eff4.png]

## ?[相交链表][Link 1] ##

### ?题目描述 ###

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

图示两个链表在节点 c1 开始相交：  
![在这里插入图片描述][e5f5e76ce3014fb9a83b1da961ce3797.png]

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

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

### ?示例 ###

#### ?示例一 ####

![在这里插入图片描述][cc9a80af0f6845a1a43f7d2f44bf9dd2.png]

#### ?示例二 ####

![在这里插入图片描述][3b48f12a6bfe4210b51493e89b5fe503.png]

#### ?示例三 ####

![在这里插入图片描述][a638ccf2ac144899a617ebb98c96ed64.png]

### ?解法思路 ###

我们发现，两个链表如果相交  
![在这里插入图片描述][e06d2badbf614061b7e7140f7463cad0.png]  
那我们就可以让长链表先走等于它们之间差值的步数

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

#### ?相关变量的建立 ####

我们将

*  长的链表用指针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; 
        }
    }

## ?[环形链表][Link 2] ##

### ?题目描述： ###

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

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

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

### ? 示例 ###

#### ?示例一 ####

![在这里插入图片描述][fbbca78a76264f0ba2ed9b5a08fa9829.png]

#### ?示例二 ####

![在这里插入图片描述][1a0e31e1df9f4d63baef0ea7df2b2acc.png]

#### ?示例三 ####

![在这里插入图片描述][347989d6738946c095c275acd6ab936a.png]

### ?思路解析： ###

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

比如环形操场上跑步：  
![在这里插入图片描述][6bffcff7194947098fe04fa434d1cd23.png]

### ?扩展问题 ###

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

快指针一次走3步，走4步，…n步行吗？

*  ![在这里插入图片描述][6f089068d12447a3b4ceb4fdb268a9bb.png]

### ?完整代码： ###

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

## ?[环形链表||][Link 3] ##

### ?题目描述： ###

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

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

不允许修改 链表。

### ?示例 ###

#### ?示例一 ####

![在这里插入图片描述][743d1f4b33b8435194725676ec7cde90.png]

#### ?示例二 ####

![在这里插入图片描述][e89e743a810940bbb1e2f6b460a73487.png]

#### ?示例三 ####

![在这里插入图片描述][67c6bddee34b45fc93c3a49eb1bb11b5.png]

### ?思路解析： ###

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

图解如下：  
![在这里插入图片描述][b273985c42994c20ad8568fcf186ee41.png]

### ?完整代码 ###

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

## ⭕总结 ##

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

[94b094fa0d0f42bcac0a437a41e1eff4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/a9892c867f424775958e0c1e90019eaf.png
[Link 1]: https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
[e5f5e76ce3014fb9a83b1da961ce3797.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/a0288ce84a6b4c8ba377b98979df25d7.png
[cc9a80af0f6845a1a43f7d2f44bf9dd2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/c0fa6a9e9dd74431b25bd40a1756f32e.png
[3b48f12a6bfe4210b51493e89b5fe503.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/bb195b0805e64209823603bb61025823.png
[a638ccf2ac144899a617ebb98c96ed64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/7fa746d030014ce299e6ccc0438cf6a7.png
[e06d2badbf614061b7e7140f7463cad0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/323c77abe0a3482fa7ba3732a2de2f6e.png
[Link 2]: https://leetcode.cn/problems/linked-list-cycle/description/
[fbbca78a76264f0ba2ed9b5a08fa9829.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/4bfe720c9e6143169897c163dad0f902.png
[1a0e31e1df9f4d63baef0ea7df2b2acc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/45f9615a38f342e49aac9c11bb2891ed.png
[347989d6738946c095c275acd6ab936a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/afa491e80e334c64bcf6766aa7db07eb.png
[6bffcff7194947098fe04fa434d1cd23.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/1ac6019407ba4db9a00ad0fd25d37898.png
[6f089068d12447a3b4ceb4fdb268a9bb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/e4e1095aedd443f48dcabad2442628a8.png
[Link 3]: https://leetcode.cn/problems/linked-list-cycle-ii/description/
[743d1f4b33b8435194725676ec7cde90.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/c1a0974526a44d38916a3c60ff078181.png
[e89e743a810940bbb1e2f6b460a73487.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/0a204ed193ad459b8329bc41d779e8c5.png
[67c6bddee34b45fc93c3a49eb1bb11b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/e4e8ab969d524040854cf376d1643cb8.png
[b273985c42994c20ad8568fcf186ee41.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/d1be2d9a1d3d4564baddf40366d37389.png