链表面试题(图文详解)

🎉🎉🎉写在前面：
博主主页：🌹🌹🌹戳一戳，欢迎大佬指点！
博主秋秋：QQ：1477649017 欢迎志同道合的朋友一起加油喔💪
目标梦想：进大厂，立志成为一个牛掰的Java程序猿，虽然现在还是一个小菜鸟嘿嘿
-----------------------------谢谢你这么帅气美丽还给我点赞！比个心-----------------------------

面试经典例题

1，删除链表中所有等于定值val的节点

Leetcode传送门，点击这里！！

classSolution{publicListNoderemoveElements(ListNode head,int val){if(head ==null){returnnull;//链表为空}ListNode prev = head;ListNode cur = head.next;while(cur !=null){if(cur.val == val){
                cur = cur.next;
                prev.next = cur;}else{
                prev = cur;
                cur = cur.next;}}//特殊情况，头节点也为keyif(head.val == val){
            head = head.next;}return head;}}

这个题的解答其实和我们的单链表的模拟实现的removeAllKey()是一个意思，所以具体的解析大家看这张图。

2，反转一个单链表

Leetcode传送门，点击这里！！

//要求原地进行反转//1,只用一个节点指针，进行头插classSolution{publicListNodereverseList(ListNode head){if(head ==null){returnnull;}ListNode cur = head.next;
        head.next =null;while(cur !=null){ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;}return head;}}//2，两个节点指针，原地逆序classSolution{publicListNodereverseList(ListNode head){if(head ==null){returnnull;}ListNode prev = head;ListNode cur = head.next;
        head.next =null;while(cur !=null){ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;}
        head = prev;return head;}}

【图示：第一种方法】

【图示：第二种方法】

3，寻找中间节点

具体题目：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点

Leetcode传送门，点击这里！！

可能有的同学会觉得很简单，先遍历一遍求出长度，然后不就顺理成章的知道中间节点了嘛。但是，面试题的要求肯定不会让你如此，假如要求你只能遍历一遍就把问题解决，那你如何做呢？

//这里用到了 快慢指针 的思想classSolution{publicListNodemiddleNode(ListNode head){ListNode fast = head;ListNode slow = head;while(fast !=null&& fast.next !=null){
            fast = fast.next.next;
            slow = slow.next;}return slow;}}

【图示：】

这里解释一下快慢指针的原理，因为它是找到中间节点，我们的fast与slow指针的起点一样，路程也一样，但是fast的速度是slow的二倍，这样当我们的fast走到终止时，slow的位置就是我们要求的中间节点。

4，链表中倒数第K个节点

牛客传送门，点击这里！！

//要求还是只让你遍历一遍链表importjava.util.*;publicclassSolution{publicListNodeFindKthToTail(ListNode head,int k){if(head ==null){returnnull;}if(k <=0){//判断k的合法性returnnull;}ListNode fast = head;ListNode slow = head;while(k -1!=0){//让fast先走k-1步
            fast = fast.next;if(fast ==null){returnnull;//说明k过大}
            k--;}while(fast.next !=null){//fast.next == null 就说明fast到了最后节点了，就不走了
            fast = fast.next;
            slow = slow.next;}return slow;}}

这个题还是快慢指针的思想。它既然想找到我们的倒数第k个节点，我们就想让fast先走k-1步，这样的话，等到fast到最后一个节点时，slow的位置就是我们的倒数第k个节点处。这里的关键就是我们的倒数第k个节点与我们的最后一个节点之间差的就是k-1步，这也是为什么要将fast先走k-1步的原因。

【图示：】

while(k -1!=0){//让fast先走k-1步
    fast = fast.next;if(fast ==null){returnnull;//说明k过大}
    k--;}

这里还有一个点就是我们的k肯定是不能大于我们的链表长度的，但是要求是只能遍历一遍链表，所以我们没办法去求链表的长度，但是我们知道，限制k不能过大的原因就是fast走的时候可能直接变成null了，所以我们可以把这个条件转换到这里的先走k-1步中，因为假设我们的链表长度是len，那么极端情况就是求倒数第len个，那么fast最多先走len-1步，所以如果当k> size()的时候，k-1 >= size()，明显就不符合了，fast在移动的过程中就会变成null，这个时候就说明k过大了。

5，合并两个有序链表

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

Leetcode传送门，点击这里！！

classSolution{publicListNodemergeTwoLists(ListNode list1,ListNode list2){ListNode newNode =newListNode(-1);//虚拟节点ListNode tmp = newNode;while(list1 !=null&& list2 !=null){if(list1.val < list2.val){
                tmp.next = list1;
                tmp = list1;
                list1 = list1.next;}else{
                tmp.next = list2;
                tmp = list2;
                list2 = list2.next;}}if(list1 ==null){//也包含初始条件下某一个就为null的情况
            tmp.next = list2;}if(list2 ==null){
            tmp.next = list1;}return newNode.next;//然会新的头节点，原两个链表的头节点都动了}}

看到这个题呢，可能很多同学会想起合并两个有序数组，这二者之间确实有着异曲同工之妙，不一样的是这里我不需要额外的空间，因为链表我可以直接改变next域让其串起来，即使是两个链表的元素。同样是指针遍历，list1,list2两个节点指针去遍历元素，tmp记录当前所在元素的位置。

【图示：】

6，分割链表

具体题目：编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。

牛客传送门，点击这里！！

importjava.util.*;publicclassPartition{publicListNodepartition(ListNode pHead,int x){ListNode as =null;ListNode ae =null;ListNode bs =null;ListNode be =null;ListNode cur = pHead;while(cur !=null){if(cur.val < x){if(as ==null){//可能是放入第一个数据
                    as = cur;
                    ae = cur;}else{
                    ae.next = cur;
                    ae = ae.next;}}else{if(bs ==null){
                    bs = cur;
                    be = cur;}else{
                    be.next = cur;
                    be = be.next;}}
            cur = cur.next;}//然后把两个段链接起来if(as ==null){//有可能没有第一段return bs;//bs也有可能是null}
        ae.next = bs;//把两段连起来，如果第二段不存在，刚好用来把第一段结尾置为nullif(bs !=null){//如果存在第二段，那么第二段的尾巴需要手动置null一下
            be.next =null;}return as;}}

【图示：】

7，链表的回文结构

牛客传送门，点击这里！！

importjava.util.*;publicclassPalindromeList{publicbooleanchkPalindrome(ListNode head){if(head ==null){returntrue;//空链表算回文}ListNode fast = head;ListNode slow = head;//先找到中间节点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;}//翻转完毕，slow现在在最后一个节点处while(head != slow){if(head.val != slow.val){returnfalse;}if(head.next == slow){returntrue;}
            head = head.next;
            slow = slow.next;}returntrue;}}

回文结构，按照面试的要求，肯定是不能用除链表之外的空间的，所以你只能原地判断。那想法肯定是前后遍历然后对比值，但是链表如何能够从后往前走呢？此时反转是不是就可以达到目的了，所以我们的思路就是
1，找到中间节点 2，从中间节点往后开始反转链表 3，判断回文。

【图示：】

8，相交链表的公共节点

Leetcode传送门，点击这里！！

publicclassSolution{publicListNodegetIntersectionNode(ListNode headA,ListNode headB){if(headA ==null|| headB ==null){returnnull;}ListNode fast = headA;//fast指向的是长的那个链表，现在假设是headA长ListNode slow = headB;int subLen =0;int lenA =0;int lenB =0;while(fast !=null){
            lenA++;//从headA计算长度
            fast = fast.next;}while(slow !=null){
            lenB++;//从headB计算长度
            slow = slow.next;}

        subLen = lenA - lenB;//因为动了fast与slow，现在重新让他们指向开头，同时更新一下fast与slow的指向if(subLen <0){
            fast = headB;
            slow = headA;
            subLen = lenB - lenA;}else{
            fast = headA;
            slow = headB;}while(subLen !=0){//让长的那一方的指针fast先走差值步
            fast = fast.next;
            subLen--;}while(fast != slow){
            fast = fast.next;
            slow = slow.next;}return fast;}}

首先我们得弄清楚一个点，两个链表相交，是怎么相交？ X 型 或者是 Y型？答案肯定是 Y型，因为我们的链表一个节点的后继肯定只有一个，所以不肯能是X型。

【图示：】

9，判断链表中是否有环

Leetcode传送门，点击这里！！

publicclassSolution{publicbooleanhasCycle(ListNode head){ListNode fast = head;ListNode slow = head;while(fast !=null&& fast.next !=null){//奇数个节点或者偶数个节点没环的终止条件
            fast = fast.next.next;
            slow = slow.next;if(fast == slow){returntrue;}}returnfalse;}}

可以看到，原理还是很简单，快慢指针的追及问题，因为如果有环存在，那么在快指针与慢指针的移动过程中，一定会相遇。但是，这里有一个关键问题就是，快指针与慢指针之间的速度差是多少？怎么确定？

答案是：快指针一次走两步，慢指针一次走一步。原因如下：

快指针肯定是先进环，慢指针后进环，那么这个时候，最好的情况就是刚好slow过来就直接和fast相遇了；最差的情况就是二者之间刚好差一个环的长度。fast指针每次走两步，slow指针每次走一步，那么每移动一次，二者之间的距离就会少一步(相对于slow，fast的每次移动都多一步，所以移动一次，中间距离就会缩小一步)，这个时候其实就是一个fast去追slow的问题，并且不会出现套圈的问题。所以，在slow把这圈走完之间，fast绝对可以把slow追上。

可能有的同学会问快指针可不可以一次走3步，或者4步，或者更多？其实我们一次只走两步，这个决定的考量就是为了防止套圈的问题出现，因为快慢指针之间的速度差越大，在某种程度上，可能会更加快的追上，但同时套圈的危险性就更大了，比如：

注意，我们是两个都走完了才开始比，移动过程中的相遇是不算的，综上，就是我们选择走两步与走一步的原因。

10，返回入环节点

具体题目：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL。

Leetcode传送门，点击这里！！

publicclassSolution{publicListNodedetectCycle(ListNode head){if(head ==null){returnnull;}ListNode fast = head;ListNode slow = head;while(fast !=null&& fast.next !=null){//奇数个节点或者偶数个节点没环的终止条件
            fast = fast.next.next;
            slow = slow.next;if(fast == slow){break;}}if(fast ==null|| fast.next ==null){//说明没有环returnnull;}//上面没有return掉，就说明有环，并且fast与slow相遇了
        fast = head;while(fast != slow){
            fast = fast.next;
            slow = slow.next;}return fast;}}

【图示：】

最后，今天的文章分享比较简单，就到这了，如果大家觉得还不错的话，还请帮忙点点赞咯，十分感谢！🥰🥰🥰