【Java数据结构】详解LinkedList与链表（二)

E绵绵

发布于 2024-06-02 08:58:26

650

发布于 2024-06-02 08:58:26

1.❤️❤️前言~🥳🎉🎉🎉

Hello, Hello~ 亲爱的朋友们👋👋，这里是E绵绵呀✍️✍️。 如果你喜欢这篇文章，请别吝啬你的点赞❤️❤️和收藏📖📖。如果你对我的内容感兴趣，记得关注我👀👀以便不错过每一篇精彩。 当然，如果在阅读中发现任何问题或疑问，我非常欢迎你在评论区留言指正🗨️🗨️。让我们共同努力，一起进步！ 加油，一起CHIN UP！💪💪
这篇文章我们将给大家带来一些单链表的面试题，都很有意思，来看一下吧。

2.反转一个单链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

我们的解决方法是依次头插法：

最开始时我们需要将第一个节点的next值变为null，使其变成最后的节点，就产生了新的链表。而后依次将原始链表中的第二个节点，第三个节点直至最后一个节点头插到新链表中。

这样就翻转成功了

完整代码如下：

public void reverseList() {
        if(head==null)
            return;
        ListNode cur=head.next;
        ListNode prev;
        head.next=null;
        while(cur!=null){
            prev=cur.next;
            cur.next=head;
            head=cur;
            cur=prev;
        }
    }

这是该题的链接： 翻转链表

3. 找到链表的中间节点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

该题的思路实现是设置两个引用：slow 慢引用和 fast 快引用

fast 和 slow 同时从head开始遍历，但是fast一次走两步，slow一次只走一步，最后我们会发现当 fast遍历完成后，对应的slow正好是链表的中间节点或者第二个中间节点。

fast遍历完成的标志是fast.next=null或者fast=null

完整代码如下：

public ListNode middleNode(ListNode head) {
     ListNode fast=head;
   ListNode  slow=head;
    while(fast!=null&&fast.next!=null){
           fast=fast.next.next;
           slow=slow.next;
    }
        return slow;
}

该题链接：求链表中间结点

4.输入一个链表，输出该链表中倒数第k个结点。

该题有两种思路

第一种思路：

第二种思路：

所以我们采用第二种思路去做题，且我们还需要注意k的合法性。

整体代码如下：

public ListNode FindKthToTail(ListNode head,int k){
if(head==null){
return null;
}
ListNode fast = head;
ListNode slow = head;
//1.判断k值的合法性
if( k<=0 ){
System.out.println("k值不合法");
return null;
}
//2.让fast 提前走 k-1 步
while(k-1>0){
if(fast == null |l fast.next ==null){
System.out.println("k值不合法”);
return null;
}
fast = fast.next;
k--;
}
while(fast !=null && fast.next != null){
fast = fast.next;slow = slow.next;
return slow;
}
}

该题题目已下架，无链接。

5.合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解题思路： 1.先创建一个新的链表 2.让cur1 和 cur2遍历两个链表，遇到的节点逐个比较，将值小的节点往新链表的末尾tail进行尾插 3.上述循环结束后，要判断有无链表还有剩余元素，把剩余的元素尾插到新链表的末尾。

完整代码如下：

public  static ListNode mergeTwoLists(ListNode list1, ListNode list2){
        //将两个有序链表合并为一个有序链表
        ListNode head1=list1;
        ListNode head2=list2;
        ListNode head=new ListNode(-1);
        ListNode cur=head;
        while(head1!=null&&head2!=null){
            if(head1.value>head2.value){
                cur.next=head2;
                cur=cur.next;
                head2=head2.next;
            }
            else{
                cur.next=head1;
                cur=cur.next;
                head1=head1.next;
            }
        }
        while(head1!=null){
            cur.next=head1;
            cur=cur.next;
            head1=head1.next;
        }
        while(head2!=null){
            cur.next=head2;
            cur=cur.next;
            head2=head2.next;
        }

        return head.next;
    }

该题链接：合并两个有序链表

6.链表分割

现有一链表的头引用 pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。解题思路： 1.创建两个链表，一个链表尾插值小于x的节点，另一个链表中插值大于等于x的节点 2.遍历原链表，将链表中的节点往两个新链表中尾插 3.将两个链表拼接
但是这种思路仍然存在较大的问题，什么问题呢?

1.我们传入的x值比节点中val都大或者都小，那么存在一个问题就是有一个链表中的内容为空，那么按照上面的思路走时，必然会出现空指针异常的情况。 解决方法: 当第一个区间为空时,那么直接返回ca 2.最后一个节点分到小于x的区间，那么最后一个节点的next并不是null，所以此时我们必须手动将 cb.next=null; 预防最后一个节点的next不是null，从而报错。

完整代码如下：

  public static ListNode partition(ListNode pHead, int x) {
        //给一定值x，该方法将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
        if(pHead==null)
            return  null;
        ListNode cur=pHead;
        ListNode  sa=null;ListNode  sb=null;   //小于x的结点所在链表
        ListNode  ca=null;ListNode  cb=null; //大于x的结点所在链表
        while(cur!=null){
            if(cur.value<x){
                if(sa==null){
                    sa=cur;
                    sb=cur;
                    cur=cur.next;
                }else{
                    sb.next=cur;
                    sb=cur;
                    cur=cur.next;
                }
            }else{
                if(ca==null){
                    ca=cur;
                    cb=cur;
                    cur=cur.next;
                }else{
                    cb.next=cur;
                    cb=cur;
                    cur=cur.next;
                } }
        }
        //拼接两个链表
        if(sa==null)
            return  ca;
        //如果不存在小于X的结点，则直接返回大于x的链表，否则按如下执行会报错
        if(ca!=null)
            cb.next=null;
          //将链表中的最后一个结点的next值变为null，防止其循环从而报错
        sb.next=ca;
        return sa;
    }

题目链接：链表分割_牛客题霸_牛客网

7. 判定链表的回文结构

解题思路实现： 1.找到链表的中间节点，找中间节点:采用快慢指针就行了 2.对链表的后半部分进行反转

3.将两个链表从前往后逐个节点进行比对，如果比对之后发现所有节点的值域都相同，则是回文链表，否则不是. 并且在循环时还需注意当链表为奇数或偶数时，判定循环结束的标志不同： 奇数是head==slow时结束 偶数是head.next=slow时结束

所以完整代码如下：

public static  boolean checkPalindrome(ListNode A) {
        //判断链表是否为回文结构
        if(A==null||A.next==null)
            return true;
        ListNode slow=A;
        ListNode fast=A;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode cur=slow.next;
        while(cur!=null){
            ListNode  curnext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curnext;
        }
        ListNode head=A;
        while(head!=slow){
            if(head.value!=slow.value)
                return false;
            if(head.next==slow)
                return true;
            head=head.next;
            slow=slow.next;
        }
        return true;
    }

注意:在执行完该方法后链表结构会被破坏掉，之后如果还对该链表进行操作，结果会和我们预想的结果不一样。

该题链接：链表的回文结构_牛客题霸_牛客网

8.输入两个链表，找出它们的第一个公共结点。

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

下面是两个节点相交的各类情况：

从上述链表相交的情况看出，两个单链表只要相交，从交点开始，到其后续所有的节点都是两个链表中公共的节点 检测两个链表是否相交:分别找到两个链表中的最后一个节点，然后检测这两个节点的地址是否相同即可：如果地址相同则相交，否则不相交

解题思路： 1.让较长的链表先走两个链表的差值步数 2.再让两个链表同时往后走，直到遇到地址相同的交点，没有则返回null

  public static  ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //给你两个单链表的头节点 headA 和 headB ，找出并返回两个单链表相交的起始节点。
            if(headA==null||headB==null)
                return null;

            ListNode cur1=headA;
            ListNode cur2=headB;
            int length1=0;
            int length2=0;
            while(cur1!=null){
                length1++;
                cur1=cur1.next;
            }while(cur2!=null){
                length2++;
                cur2=cur2.next;
            }
            cur1=headA;
            cur2=headB;
            if(length1>length2){
                for(int i=0;i<length1-length2;i++){
                    cur1=cur1.next;
                }
            }else{
                for(int i=0;i<length2-length1;i++){
                    cur2=cur2.next;
                }
            }
            while(cur1!=null){
                if(cur1==cur2)
                    return cur1;
                cur1=cur1.next;
                cur2=cur2.next;
            }
            return null;
        }

题目链接：找出两个链表的第一个公共节点

9. 判断链表中是否有环

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

解题思路：设计快慢指针去解决，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。
扩展问题： 1.为什么快指针每次走两步，慢指针走一步可以？假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现始终相遇不到的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。 2.快指针一次走3步，走4步，...n步行吗？ 假设:快指针每次走3步，满指针每次走一步，此时快指针肯定先进环，慢指针后来才进环。假设慢指针进环时候，快指针的位置如图所示:

此时按照上述方法来绕环移动，每次快指针走3步，慢指针走1步，它们是永远不会相遇的，因此不行。 只有快指针走2步，慢指针走一步才可以，因为每移动一次，它们之间的距离就缩小一步，无论如何都能相遇。 所以我们在环问题中设置快慢指针，都是将快指针设置为一次两步，慢指针一次一步，这样当存在圈时无论如何都会相遇。

完整代码如下：

 public static  boolean hasCycle(ListNode head) {
        //给你一个链表的头节点 head ，判断链表中是否有环。
        if(head==null||head.next==null)//只有一个节点时默认绝对不存在环
            return false;
        ListNode slow=head;
        ListNode  fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast)
                return true;
        }
        return false;
    }

题目链接：判断链表中是否有环

10.返回链表开始入环的第一个节点

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

解题思路：设计一个慢指针，一个快指针，快指针一次两步，慢指针一次一步。使两指针相遇而后让一个指针从链表起始位置开始遍历链表，同时也让一个指针从相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。它们肯定会在入口点相遇的证明如下：

上图中的H为链表的起始点，E为环入口点，M为慢速指针相遇点，设环的长度为R，H到E的距离为L ，E到M的距离为X，则M到E的距离为R-X 在快慢指针相遇过程时，快慢指针相遇时所走的路径长度: fast:L +X + nR slow:L+ X 注意: 1.当慢指针进入环时，快指针可能已经在环中绕了n圈了，n至少为1。 因为:快指针先进环走到M的位置，最后又在M的位置与慢指针相遇 2.慢指针进环之后，快指针肯定会在慢指针走一圈之内追上慢指针 因为:慢指针进环后，快慢指针之间的距离最多就是环的长度，而两个指针在移动时，每次它们至今的距离都缩减一步，因此在慢指针移动一圈之前快指针肯定是可以追上慢指针的 而快指针速度是满指针的两倍。 所以有如下关系是: 2 *(L+X)=L+X+nR L+X=nR L=nR-X(n为1,2,3,4..……，n的大小取决于环的大小，环越小n越大) 极端情况下，假设n=1，此时:L=R-X 所以由此得知一个指针从链表起始位置运行，一个指针从相遇点位置绕环，每次都走一步，两个指针无论如何最终都会在入口点的位置相遇。

完整代码如下：

public static  ListNode detectCycle(ListNode head) {
        //给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
        if(head==null||head.next==null)
            return null;
        ListNode slow=head;
        ListNode  fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast){
                slow=head;
                while(slow!=fast){
                    slow=slow.next;
                    fast=fast.next;
                }
                return slow;
            }
        }
        return null;
    }

11.总结

所以对于这10个面试题我们就讲述清楚了，并且我还把其中的部分题目当作特殊方法加入到模拟的无头单向非循环链表类中。对于该无头单向非循环链表的模拟实现和其具体使用放到码云里了，大家可以看下：无头单向非循环链表的模拟实现和其具体使用(此外还往模拟的链表内部添加了一些特殊方法)
下篇文章将给大家带来LinkedList的模拟实现和具体使用。在此，我们诚挚地邀请各位大佬们为我们点赞、关注，并在评论区留下您宝贵的意见与建议。让我们共同学习，共同进步，为知识的海洋增添更多宝贵的财富！🎉🎉🎉❤️❤️💕💕🥳👏👏👏