0


【Java】手撕链表笔试题(超详细解题思路)(第四期)

在这里插入图片描述


文章目录


前言

本篇博客我们一起看看链表笔试题的最后一期,看完这四期笔试题讲解后,我相信链表的各类题对大家就不再是难题了


一、Leetcode–160.相交链表

1.题目描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2.思路讲解

1.其实这个题是一个很有意思的题,它里面包含着一个严格的数学证明
在这里插入图片描述
假设此时链表A的不相交的长度为a,
在这里插入图片描述

链表B的不相交的长度为b,
在这里插入图片描述

AB相交的长度为c
在这里插入图片描述
此时神奇的地方就来了:
a + c + b = b + c + a
让headA从链表A的头结点开始走,同时让headB从链表B开始走,当headA走到链表的尾结点的时候,让headA从链表B的头结点开始走,同样,当headB走到链表的尾结点的时候,让headB从链表A的头结点开始走,此时headA和headB一定在相交链表的交点相遇
2.两个链表不相交的情况也是的一样
在这里插入图片描述
链表A的长度为a
链表B的长度为b
此时链表不相交,假设相交长度为c(c == 0)
a + c + b = b + c + a = null
在这里插入图片描述

3.代码实现

public ListNode getIntersectionNode(ListNode headA, ListNode headB){
        ListNode l1 = headA;
        ListNode l2 = headB;while(l1 != l2){//            if (l1 == null){//                l1 = headB;//            }else{//                l1 = l1.next;//            }//            if (l2 == null){//                l2 = headA;//            }else{//                l2 = l2.next;//            }
            l1 = l1 ==null? headB : l1.next;
            l2 = l2 ==null? headA : l2.next;}return l1;}

二、Leetcode–141.环形链表

1.题目描述

在这里插入图片描述
在这里插入图片描述

2.读入数据

代码如下(示例):

data = pd.read_csv(
    'https://labfile.oss.aliyuncs.com/courses/1283/adult.data.csv')print(data.head())

2.思路讲解

类比一下现实生活,学校中的操场就可以看作一个环形链表,跑的快的同学跑着跑着就能追上跑得慢的同学
我们可以引用类似的思路——快慢指针
让一个引用一次走一步,另一个引用一次走两步,
若链表带环,快指针跑着跑着一定能追上满指针,此时链表一定带环;
若链表不带环,快指针跑着跑着就走到null了
在这里插入图片描述

3.代码实现

public boolean hasCycle(ListNode head){
        ListNode fast = head;
        ListNode low = head;while(fast !=null&& fast.next !=null){
            fast = fast.next.next;
            low = low.next;if(fast == low){returntrue;}}returnfalse;}

三、Leetcode–142.环形链表||

1.题目描述

在这里插入图片描述

2.思路讲解

本题和上题不同,找到带环链表的入口,返回入口结点,若没有环,返回null
在这里插入图片描述
在这里插入图片描述
a.带环链表的直线长度
b.从环的入口到两个指针相遇的位置的距离
c.相遇位置到环入口的剩下的环状长度
现在已知快指针的速度是慢指针的两倍,而且跑了相同的时间,那么快指针的路程也是慢指针的两倍
快指针走的路程:a + n(b + c) + b
慢指针走的路程:a + b

由快指针的路程是慢指针的两倍得到关系式:
a + n(b + c) + b =2(a + b) -->
n(b + c) = a + b -->
(n - 1) (b + c) + c = a
此时假设n = 1,就可以得出a = c,直线长度和相遇点到入口剩下环的长度相等,那么当快慢指针相遇时,引入第三个指针从head开始走,一定会和慢指针在环的入口相遇!!

3.代码实现

public ListNode detectCycle(ListNode head){
        ListNode fast = head;
        ListNode low = head;while(fast !=null&& fast.next !=null){
            fast = fast.next.next;
            low = low.next;if(fast == low){
                ListNode third = head;while(third != low){
                    low = low.next;
                    third = third.next;}return low;}}returnnull;}

四、Leetcode–92.反转链表||

1.题目描述

在这里插入图片描述

2.思路讲解

1.迭代写法:三指针 + 头插
引入两个引用
prev – > 指向待反转链表的前驱结点
cur – > 指向待反转链表的第一个结点
next – > 暂存一下下一个要处理的结点
在这里插入图片描述
在这里插入图片描述
2.递归写法

3.代码实现

1.迭代写法

public ListNode reverseBetween(ListNode head, int left, int right){
        ListNode dummyHead =newListNode();
        dummyHead.next = head;
        ListNode prev = dummyHead;
        ListNode cur = prev.next;for(int i =0; i < left -1; i++){
            prev = prev.next;
            cur = cur.next;}//反转right - left次即可for(int i =0; i < right - left; i++){
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = prev.next;
            prev.next = next;}return dummyHead.next;}

2.递归写法

/**
     * 递归
     * @param head
     * @param left
     * @param right
     * @return
     */
    ListNode sucessor =null;public ListNode reverseBetween(ListNode head, int left, int right){if(left ==1){returnreverseN(head,right);}
        head.next =reverseBetween(head.next,left -1,right -1);return head;}public ListNode reverseN(ListNode head,int n){if(n ==1){
            sucessor = head.next;return head;}
        ListNode next = head.next;
        ListNode newHead =reverseN(head.next,n -1);
        next.next = head;
        head.next = sucessor;return newHead;}

本文转载自: https://blog.csdn.net/weixin_57011679/article/details/124762181
版权归原作者 萝诗粉 所有, 如有侵权,请联系我们删除。

“【Java】手撕链表笔试题(超详细解题思路)(第四期)”的评论:

还没有评论