devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

链表经典面试题（含图解）_面试题 链表操作

作者：小小林熬夜学编程 | 2024-05-04 20:33:27

赞

踩

面试题 链表操作

文章目录

一、删除链表中等于给定值 val 的所有节点

对应leetcode题

因为要删除某一个结点，就要遍历到该结点之前的位置。为了记录需要删除的结点的前一位置，我们需要另外创建一个指针pre来记录。先不对头结点进行判断它的val值是否等于val，因此只需将cur设为头结点的后一个结点即可。若先对头指针判断，则可能需要不断地改变头指针，会非常麻烦。因此先遍历整个链表，如果遇到有需要删除的结点，则有pre.next=cur.next；cur=cur.next；否则pre=cur;cur=cur.next;
如果23为需要删除的结点，则有以下的例子：
图解：
在这里插入图片描述
遇到需要删除的结点：pre.next=cur.next；cur=cur.next
在这里插入图片描述
遇到不需要删除的结点：当cur为空时，则退出循环。遍历结束后还要判断头结点的 值是否等于val。
在这里插入图片描述
代码示例：

 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null) {
            return null;
        }
        ListNode cur = head.next;
        ListNode pre = head;
        while(cur!=null) {
            if(cur.val==val) {
                pre.next=cur.next;
                cur=cur.next;
            } else {
                pre=cur;
                cur=cur.next;
            }
        }
        if(head.val==val) {
            head=head.next;
        }
        return head;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

二、反转单链表

对应leetcode题
对应如图所示：
在这里插入图片描述
为了反转链表，我们需要设置三个引用，因为一个要记录前面的位置pre，一个要记录后面的位置curNext，还有一个要作为链接链表的点cur。因为头结点会随着反转链表的改变而改变，因此要设置一个新的头结点newHead。

代码示例：

 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        ListNode curNext = null;
        ListNode newHead = null;
        while(cur!=null) {
            curNext=cur.next;
            if(curNext==null) {
                newHead=cur;
            }
            cur.next=pre;
            pre=cur;
            cur=curNext;
        }
        return newHead;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

三、找链表的中间结点

对应leetcode题
寻找中间结点，我们要找到路程与速度的规律。速度两倍的路程也是两倍，因此说明我们可以设置两个指针来走，如果一个指针是另一个指针速度的两倍，当它走到链表尾时，则另一个指针在链表的中间，因此走的慢的那个指针的位置就是中间结点的位置。但是有两种情况：第一种是单链表的结点数为奇数，第二种是单链表的结点数为偶数。

在这里插入图片描述
在这里插入图片描述
因此有两种情况：结点数为偶数时判断fast.next是否为null，结点数为奇数时判断fast是否为null。当两种情况下只有一种情况满足，则直接返回slow指针即可找到中间结点。

 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        if(head==null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

四、找链表中的第k个结点

对应leetcode题
我们用双指针来解这道题。我们发现，如果倒数第三个结点走到最后一个结点需要2步，如果倒数第二个结点走到最后一个结点需要1步，因此有这样的规律：从第k个结点开始走到最后一个结点需要走k-1步。我们假设头结点就是“最后一个结点”，因此让一个fast指针走k-1步，此时是链表倒置的第k个结点。而此时两个指针同时走，当发现fast指针走到fast.next值为null时，则找到第k个结点，第k个结点的位置就是slow指针所指向的位置。slow与fast一开始指向head。
图解：
fast走k-1步：
在这里插入图片描述
fast与slow同时走，判断条件为fast.next不为null
在这里插入图片描述
代码示例：

public ListNode getKthFromEnd(ListNode head, int k) {
        if(head==null) {
            return null;
        }
        if(k<0) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(k-1!=0) {
            fast=fast.next;
            if(fast==null) {
                return null;
            }
            k--;
        }
        while(fast!=null&&fast.next!=null) {
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

五、合并两个有序链表

对应leetcode题
此处我们设置一个新的头结点，将两个单链表串起来。因为是按照升序来连接链表，因此每次都需要判断l1的值与l2的值谁大谁小，小的先连接。而为了新的头结点不改变，需要另一个指针从头结点开始对l1或者l2连接。因为l1与l2的长度可能不同，因此有可能会先连完一条链，而另一条链直接连在新的链表当中即可。
图解：准备工作：
在这里插入图片描述

 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newHead = new ListNode();
        ListNode tmp = newHead;
        if(l1==null&&l2==null) {
            return null;
        }
        if(l1==null) {
            newHead.next=l2;
        }
        if(l2==null) {
            newHead.next=l1;
        }
        while(l1!=null&&l2!=null) {
            if(l1.val>l2.val) {
                tmp.next=l2;
                l2=l2.next;
                tmp=tmp.next;
            } else {
                tmp.next=l1;
                l1=l1.next;
                tmp=tmp.next;
            }
        }
        if(l1==null) {
            tmp.next=l2;
        }
        if(l2==null) {
            tmp.next=l1;
        }
        return newHead.next;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

六、分隔链表

对应leetcode题
为了分开链表中小于val值得结点，我们设置两个新的链表，用空间来换取时间。因此两个新的链表有头结点与临时结点。一边放入小于val值的结点，另一边放入大于和等于val值的结点。但放入结点时有两种情况。第一种情况时第一次放入时，两个新的链表都无指向，因此第一次应该直接指向原来的链表中即可。除了第一次为特殊情况外，新的链表的指针指向的都是原来的链表中cur遍历所指向的该结点。而临时指针也需要向后移一位。而cur也需要后移一位。
需要注意的是：

  1. 如果bs为null则需要改变be的next值为null，否则还会指向某一个结点。
  2. 如果as为null则直接返回bs即可。
  3. 最后将两个新的链表合起来，则需要有ae.next=bs;
    图解：
    在这里插入图片描述
    代码示例：
    public ListNode partition(ListNode head, int x) {
        ListNode as = null;
        ListNode ae = null;
        ListNode bs = null;
        ListNode be = null;
        ListNode tmp = head;
        while(tmp!=null) {
            if(tmp.val<x) {
                if(as==null) {
                    as=tmp;
                    ae=tmp;
                } else {
                    ae.next=tmp;
                    ae=ae.next;
                }
            } else {
                if(bs==null) {
                    bs=tmp;
                    be=tmp;
                } else {
                    be.next=tmp;
                    be=be.next;
                }
            }
            tmp=tmp.next;
        }
        if(as==null) {
            return bs;
        }
        ae.next=bs;
        if(bs!=null) {
            be.next=null;
        }
        return as;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

七、删除排序链表中的重复元素

对应leetcode题
因为一个链表中重复的元素有多个，并且要求全部删除，则我们需要一个循环来遍历链表并且创建指针cur从头结点开始，判断cur.val==cur.next.val，如果相等则跳过重复的元素。当然此时要注意要判断cur.next一定不能为null，否则cur.next.val会空指针异常。示例如下：
在这里插入图片描述
但是tmp需要连接的是第三个结点，因此cur此时还要向后移一位。才有tmp.next=cur;cur=cur.next;tmp=tmp.next但是cur.next已经为null了，因此要退出循环。再将tmp.next=null 。

代码示例：

 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode newHead = new ListNode(-1);
        ListNode cur = head;
        ListNode tmp = newHead;
        while(cur!=null) {
            if(cur.next!=null&&cur.val==cur.next.val) {
                while(cur.next!=null&&cur.val==cur.next.val) {
                    cur=cur.next;
                }
                cur=cur.next;
            } else {
                tmp.next=cur;
                cur=cur.next;
                tmp=tmp.next;
            }
        }
        tmp.next=null;
        return newHead.next;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

八、判断一个链表是否是回文链表

对应leetcode题
回文链表指的是链表两边的结点的值对称，如果为奇数不用判断中间部分。我们第一步首先创建两个指针slow和fast，让slow走到中间结点的位置，就等同于找中间结点。第二步逆置slow后半部分的链表。就等同于逆置链表，思想上是一样的。第三步是从head结点和slow结点处遍历前半部分与后半部分链表。如果对应结点有不相同的val值，则返回true。
图解：
在这里插入图片描述
注意
1.slow走到中间时创建cur指针与curNext指针对链表进行逆置。当slow到达最后一个结点的条件为cur!=null。
2.判断是否是回文链表，则情况有两种。第一种是结点数量为奇数时有head!=slow，第二种是结点数量为偶数时有head.next!=slow。

结点数为偶数时需要判断：如果能够走到head与slow相遇则返回true，否则返回false。
在这里插入图片描述

结点数为偶数时需要判断head.next==slow，否则在链表中如果head与slow“擦肩而过”等同于不相遇。
在这里插入图片描述

代码示例：

 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode A) {
        if(A==null) {
            return true ;
        }
        ListNode fast = A;
        ListNode slow = 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;
        }
       while(A.val==slow.val) {
           if(A.next==slow||A==slow) {
               return true;
           }
           A=A.next;
           slow=slow.next;
       }
        return false;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

九、两个链表的第一个公共节点

对应leetcode题
找两个链表的公共结点，首先想到的是先设置两个指针从两个链表的头开始，让相对长的链表先走两个链表的长度差值，再让两个指针一起走，相遇的点就是它们的公共点。我们假设p1指向的始终是较长的链表，p2指向的是较短的链表。因此可以分为三步：第一步求出两个链表的长度的差值；第二步让链表走长度差值步。第三步让两个指针一起走，判断的终点为两个指针相遇。
图解：
在这里插入图片描述

代码示例1：这种相对来说好理解一些。

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null) {
            return null;
        }
        ListNode pl = headA;
        ListNode ps = headB;
        int lenA = 0 ;
        int lenB = 0 ;
        while(pl!=null) {
            pl=pl.next;
            lenA++;
        }
        pl=headA;
        while(ps!=null) {
            ps=ps.next;
            lenB++;
        }
        ps=headB;
        int len = lenA-lenB;
        if(len<0) {
            pl=headB;
            ps=headA;
            len = lenB-lenA;
        }
        while(len!=0) {
            pl=pl.next;
            len--;
        }
        while(pl!=ps) {
            pl=pl.next;
            ps=ps.next;
        }
        return pl;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

代码示例2：这种代码可读性不太强，但是更加简洁，原理相同。

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

十、判断一个链表是否有环

对应leetcode题
设置两个指针fast和slow，都从头结点处开始走，fast指针一次走两步，slow指针一次走一步，如果最后相遇，则该链表肯定有环。如果fast指针为null，则该链表不是环形链表。
图解：
在这里插入图片描述

代码示例：

 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null) {
            return false;
        }
        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;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

十一、判断一个链表是否有环，并返回第一个结点

对应leetcode题
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果该链表是一个环形链表，则它的形状如下图所示。我们设直线的起始位置为起始点，长度为a，而在走过长度b后在该小圆点处相遇。而长度c等于一个环的周长减去b。因此我们仍然可以设置双指针fast和slow。fast指针一次走两步，slow指针一次走一步。因此slow与fast指针在环中相遇时，fast有可能走了n圈环，而slow最多只可能走了一圈，而fast走的路程又是slow走的路程的两倍。因此有以下公式：fast走的路程=a+n(b+c)+b，而slow走的路程=a+b。因此有a+n(b+c)+b=2(a+b)，化简得a=c+(n−1)(b+c)。因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。（slow可能走很多圈，但是从相遇处开始一步一步走一定会相遇，相遇时返回slow或ptr指针即可）。

图解：
在这里插入图片描述
代码示例：

 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow) {
                ListNode pre = head;
                while(pre!=slow) {
                    pre=pre.next;
                    slow=slow.next;
                }
                return pre;
            }
        }
        return null;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/536060
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号