【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;}