[数据结构与算法]十一道链表常考面试题【详解篇12】

链表常考面试题

一、【Leetcode】203移出链表元素

203移出链表元素

【题目描述】：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点

这个题和单链表中删除所有值为key的节点removeAllKey方法一样。

/**
 * Definition for singly-linked list.
 * 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) {
         //removeElements这个函数已经给了头节点head,所以不需要加this了
    if(head == null){
        return null ;
    }
    ListNode prev=head;
    ListNode cur=head.next;
    while(cur!=null){
        if(cur.val==val){
            prev.next=cur.next;
            cur=cur.next;
        }else{
            prev=cur;
            cur=cur.next;
        }
    }
    if(head.val==val){
        head=head.next;
    }
    return head;//返回 新的头节点
    //返回的ListNode实质上是删除完所有val之后的头节点，把删除之后的头返回
       
    }
}

二、【Leetcode】206反转链表（链表逆置）

206反转链表

【题目描述】：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

逻辑分析如下：

我们先画出一个单链表，根据这个单链表进行逻辑分析。

反转一个单链表也就是逆置一个单链表，那么逆置链表就是逆置数据吗？请思考…

下面这个图是我们本题最终想要的结果吗？

很明显，不是我们想要的结果，为什么呢？

因为已经打叉了? 呵呵，当然不是，想要解决这个问题，我们就要清楚，逆置链表不是逆置数据，逆置不是将数据逆置，逆置的真正要求是节点本身也要进行逆置。

那他是如何逆置的呢？或许我们可以用头插法的方式去思考这一问题

定义一个cur代表当前需要反转的节点，再定义一个curNext用来记录它的下一个节点，用curNext记录说明要修改当前节点cur的next.

疑问：为什么要定义newHead呢？

newHead是最新的头结点，但是在整个走得过程中newHead又充当了每一个节点的前驱这样一个角色。

这样说是什么意思呢？

因为上面反转的逻辑跟头插法的逻辑类似，因此可以把newHead当作每个节点的前驱prev来看，合理地利用了头插法的性质。

分析如图：

完整代码如下：

/**
 * Definition for singly-linked list.
 * 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) {
        // if(head==null)//单链表为空的情况
        // return null;//单链表为空也可以返回head
        // if(head.next==null)//第一个节点为空的情况
        // return head;
        if(head==null || head.next==null) return head;
        ListNode cur=head;
        ListNode newHead=null;
        while(cur!=null){//cur不等于空说明链表没有遍历完
            ListNode curNext=cur.next;
            cur.next=newHead;
            newHead=cur;
            cur=curNext;
        }
        return newHead;
    }
}

三、【Leetcode】876 链表的中间结点

876 链表的中间结点

【题目描述】：给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

要求：只走一遍链表就能找到中间节点

如果利用求长度的方法来解决这个问题，需要遍历两次链表才能完成，我们要求只走一遍链表就能找到中间节点，所以可以使用另外一个方法（即快慢节点数）。

画图分析逻辑：

总结：当节点数为奇数是，fast走两步,slow走一步，当fast走到fast.next为null时，slow就走到了中间节点。

总结：节点数为偶数时，fast走两步,slow走一步，当fast走到fast为null时，slow就走到了中间节点。

/**
 * Definition for singly-linked list.
 * 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){//判断头结点是否为null,为null就没有中间节点了，就返回head
            return head;
        }
          ListNode fast=head;
          ListNode slow=head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;//fast走两步
            slow=slow.next;//slow走一步
        }
        return slow;
    }
}

四、【剑指offer】链表中倒数第k个结点

链表中倒数第k个结点

【题目描述】：输入一个链表，输出该链表中倒数第k个结点。

• len-要找的倒数第几个节点=要走的步数，走完之后就找到了该链表中的倒数第k个结点
• len-k=要走的步数

分析如图：

这个方式也需要遍历两次链表，不是最佳的考虑。

这个我们也可以考虑试着遍历一次列表就解决该问题。

让快的指针（引用）先走一步，然后快引用fast和慢引用slow再同时走，当fast走到fast.nex为null时，slow所指的节点就是倒数第K个节点。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null){
            return null;
        }
        if(k<=0){//如果k不合法
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        //先让fast走k-1步
        while(k-1!=0){
            if(fast.next!=null){//如果节点数小于k,k不合法
                 fast=fast.next;
                 k--;
            }else{
                return null;
            }
        }
        //走完k-1步，fast和slow一起走
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

五、【Leetcode】21合并两个有序链表

21合并两个有序链表

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

逻辑分析：

• 定义一个虚拟节点newHead,初始值为null，他一直是新的链表的头节点
• 只要headA和headB这两个引用不为空时，分别比较他们两个的data值，谁小就把谁串到虚拟节点newHead的后面，newHead不能动，在newHead这个节点处定义一个tmp,每次让tmp.next 等于当前串过来的节点，然后让tmp等于tmp的下一个节点（tmp指向tmp的下一个节点）。

/**
 * Definition for singly-linked list.
 * 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 headA, ListNode headB) {
        //如果两个链表一个为空，一个不为空,返回不为空的链表
        if(headA==null){
            return headB;
        }
        if(headB==null){
            return headA;
        }
        //如果两个链表都为空，返回null
        if(headA==null && headB==null){
            return null;
        }
           ListNode newHead=new ListNode(-1);
           ListNode tmp=newHead;
        //如果两个链表都不为空， 比较两个链表的val值
        while(headA!=null && headB!=null){
            if(headA.val < headB.val){
                tmp.next=headA;
                headA=headA.next;//headA往后走
            }else{
                tmp.next=headB;
                headB=headB.next;//head 往后走
            }
            tmp=tmp.next;//换完之后tmp也往后走
        }
        if(headA==null){
            tmp.next= headB;
        }
        if(headB==null){
            tmp.next= headA;
        }
        return newHead.next;//newHead是一个虚拟头节点的，而链表真正的节点是不带头的
    }
}

六、【牛客网-程序面试宝典】 CM 11 链表分割

CM 11 链表分割
【题目描述】：现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

先考虑两个问题：

1.判断比定值大的该如何处理，比定值小的该如何处理？

2.如何保证比较之后数据前后顺序不变？

解决问题思路：

• 用尾插法

• 写一段按照原来顺序不变小于定值x的代码，再写一段按照原来顺序不变的大于定值x的代码，将两端代码拼接起来。

• 将小于x的开始定义为bs（beginstart）,将小于x的结束定义为be(beginend),将大于等于x的开始定义为as,将大于等于x的结束定义为ae最后让be和as连接起来。

  如图：

简单点就是：

逻辑分析如下图：

注意：链表的最后一个节点的next不是null，会导致代码死循环，也有可能bs本身就为null.

链表分割代码示例：

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
          ListNode cur=pHead;
            ListNode bs=null;
            ListNode be=null;
            ListNode as=null;
            ListNode ae=null;
            while(cur!=null){//说明链表没遍历完
                if(cur.val<x){
                    //第一部分第一次插入
                    if(bs==null){
                        bs=cur;
                        be=cur;
                    }else{
                        be.next=cur;
                        be=be.next;
                    }
                }else{
                    //第二部分第一次插入
                    if(as==null) {
                        as = cur;
                        ae = cur;
                    }else{
                        ae.next=cur;
                        ae=ae.next;
                    }
                }
                cur=cur.next;
            }
           if(bs==null){//说明第一部分为null，也就是没有小于x的数据,那就返回后一段
                return as;
            }
            //bs!=null
            be.next=as;//如果第一部分前面不为null，那就将第一部分结束和第二部分开始拼接一起
            if(as!=null){
                ae.next=null;
            }
            return bs;
        }
}

七、【剑指offer】JZ56 删除链表中重复的结点

JZ56 删除链表中重复的结点
【题目描述】：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。

逻辑分析：因为已经是排好序的，所以一样的节点一定是排在一起的。

1、设置一个新的虚拟节点（傀儡节点）newHead，来标识新节点的头结点, cur用来遍历原来的链表。

2、如果cur.val=cur.next.val说明第一个节点是重复的，如果不等于，说明第一个节点不是重复的，就把这个节点放到newHead的后面，因为newHead不能动，所以给他再定义一个tmpH,让tmpH的next就等于当前的cur,然后让tmp=tmp.next往后走，cur=cur.next往后走。

删除链表中重复的结点代码如下：

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
         ListNode newHead=new ListNode(-1);//定义一个虚拟节点newHead
        ListNode tmp=newHead;
        ListNode cur=pHead;
        while(cur!=null){
            //cur.next!=null:判断是不是只有一个节点或者是不是尾巴节点
            if(cur.next!=null && cur.val==cur.next.val){
                //cur在走的过程中有可能剩下的数据都是相同的，所以需要加上cur.next!=null 这个条件
                //否则会出现空指针异常
                while(cur.next!=null && cur.val==cur.next.val){
                    cur=cur.next;
                }
                cur=cur.next;//让cur 多走一步，就能跳过上一个重复的节点。
            }else{
                tmp.next=cur;
                tmp=tmp.next;//将节点串起来，tmp往后走
                cur=cur.next;//cur往后走
            }
        }
        tmp.next=null;//手动设置，防止最后一个节点是重复的，避免死循环
        return newHead.next;
    }
 }

八、【2016校招真题在线编程】OR36 链表的回文结构

OR36 链表的回文结构（头条、字节跳动的常考题型）

【题目描述】：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1
返回：true

疑问1:如果定义两个引用cur1和cur2，cur1从头往后走，cur2从尾往前走？这个方法可行吗？

不可行，因为是单向链表，我们都不知道cur2的前一个节点是什么。

解决问题：

先找到这个链表的中间节点，反转中间节点之后的链表。

逻辑分析：

1.那如何找链表的中间节点呢？

• 定义一个fast和slow,让fast一次走两步，slow一次走一步，当fast.next为null时，slow就是这个链表的中间节点。

2.中间节点找到后，该怎么反转呢？

• 这个中间节点slow相当于后一个节点的前驱，将后一个节点定义为cur，fast指向的节点定义为curNext，用来记录cur.next的值，让cur.next的值等于slow的值，slow指向cur,cur=curNext,cur不等于null,curNext往后走一步，即curNext=cur.next;

3.反转之后，一前一后判断，head往后走，slow往前走，直到他俩相遇，判断的原则是，head和slow的data值不一样，就直接反回false。

画图分析如下：

回文结构代码如下：

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
   if(A==null){
            return true;
        }
        if(A.next==null){
            //只有一个节点,一个节点也是回文节点
            return true;
        }
     //1.找中间节点
     ListNode slow = A;
     ListNode fast = A;
     while (fast != null && fast.next != null) {//分为奇数和偶数的情况下
         fast = fast.next.next;
         slow = slow.next;
     }
     //slow指向的节点就是这个链表的中间节点。
     //2.进行翻转
     ListNode cur = slow.next;
     while (cur != null) {//只有cur不等于null,才能继续往下走
         ListNode curNext = cur.next;
         cur.next = slow;
         slow = cur;
         cur = curNext;
     }
     ///反转完毕，slow所指向的就是最后一个节点
     //3.判断回文，看slow和head相遇结果是否相等
     while (slow != A) {
         if (slow.val != A.val) {
             return false;
         }
         if(A.next==slow){//如果链表为偶数个节点的话（不太明白。1:29:00）
             return true;
         }
         A = A.next;
         slow = slow.next;
     }
     return true;
 }
}

九、【Leetcode】141. 环形链表

141. 环形链表
【题目描述】：给定一个链表，判断链表中是否有环。如果链表中存在环，则返回 true 。 否则，返回 false 。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

什么是有环？

说人话就是，链表的最后一个节点等于它前面的某个节点的话，就表示有环。如果链表中存在环，则返回 true。 否则，返回 false 。

逻辑分析：定义一个fast再定义一个slow,fast走两步，slow走一步，每次slow走完，看fast和slow相遇了没有，如果相遇了说明这个链表是有环的。如图：

疑问1:fast一次走两步那可不可以一次走三步，四步呢？

不可以，因为有可能相遇不了，也有可能在很长的时间之后相遇。

疑问2：那为什么一次走两步就能相遇呢？

因为fast走两步slow走一步他们两个中间差的值是最小的，fast永远比slow快一步，要追上也是比较快的，如果fast走三步或4步，可能要追很久才能相遇。

环形链表I代码如下：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
         ListNode fast=head;
        ListNode slow=head;
        while(fast!=null && fast.next!=null){//有偶数或奇数的情况fast!=null用来判断偶数节点，fast.next!=null
            //用来判断奇数节点
            //如果都不为null
            fast=fast.next.next;
            slow=slow.next;
            //每次走完都要看fast和slow有没有相遇
            if(slow==fast){//如果相遇返回true
                return true;
            }
        }
        return false;//只要其中任何一个为null,就返回false
 }    
}

十、【Leetcode】142. 环形链表 II（求链表环的入口点）

142. 环形链表 II （求链表环的入口点）

【题目描述】：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

设开始到入口点之间的距离为X,入口点到相遇点的距离设置为Y,环的长度设为C

普通情况下（走一圈的情况）：

慢的路程为X+C-Y，快的路程为X+C+C-Y

快的速度是慢的速度的2倍，意味着快的路程也是慢的路程的2倍。

即2（X+C-Y）=X+C+C-Y

特殊情况下（走多圈的情况）：

慢的路程为X+C-Y，快的路程为X+NC+C-Y

快的速度是慢的速度的2倍，意味着快的路程也是慢的路程的2倍。

即2（X+C-Y）=X+NC+C-Y

画图分析：

环形链表II代码示例:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
          ListNode fast=head;
        ListNode slow=head;
        while(fast!=null && fast.next!=null){//有偶数或奇数的情况fast!=null用来判断偶数节点，fast.next!=null
            //用来判断奇数节点
            //如果都不为null
            fast=fast.next.next;
            slow=slow.next;
            //每次走完都要看fast和slow没有
            if(slow==fast){//如果相遇返回true
                break;
            }
        }
        if(fast==null || fast.next==null){//如果为空说明没有环，没有坏就返回null
            return null;
        }
        //如果循环执行结束，说明有环，有环的话，slow和fast是相遇的
        slow=head; //把slow这个引用移到前面去
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

十一、【Leetcode】160 相交链表

160 相交链表
【题目描述】：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

疑问：两个单链表相交是一种什么样的情况呢？

是一个Y字形，类似于这样

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

思路有三：

1、求两个单链表的长度

2、计算两个单链表的长度的差

3、让长的单链表先走差值步

疑问：有可能两个单链表的长度不一样，如何知道哪个长哪个短呢？

定义一个pl指向长的单链表

定义一个ps指向短的单链表

假设先默认

pl=headA

ps=headB

再定义一个lenA 、lenB、len=lenA-lenB

len=lenA-lenB

如果lenA-lenB<0,让原来默认的值换一下，即让pl=headB,ps=headA，换完之后让len=lenB-lenA;

如果lenA-lenB>0,就不用管了，说明原来默认的是正确的，len值肯定是一个正数。

IDEA下的代码写法如下：

public class TestMyLinkedList {
    //让两个单独的单链表相交的代码
    public static void createCut(ListNode headA,ListNode headB){
        headA.next=headB.next.next;
    }
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //1.求长度，走差值步
        int lenA=0;
        int lenB=0;
        ListNode pl=headA;
        ListNode ps=headB;
        //求长度
        while(pl!=null){
            lenA++;
            pl=pl.next;
        }
        while (ps!=null){
            lenB++;
            ps=ps.next;
        }
        int len=lenA-lenB;
        if(len<0){
            pl=headB;
            ps=headA;
            len=lenB-lenA;
        }
        //一定是pl指向的是最长的单链表
        for(int i=0;i<len;i++){
            pl=pl.next;
        }
        //2、ps和pl一定是在同一个起跑线上
        while(ps!=pl && pl!=null && ps!=null){
            ps=ps.next;
            pl=pl.next;
        }
        if(pl==ps && pl!=null){//代码走到这里表示pl和ps相遇了
            return pl;
        }
        return null;
    }
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();//先拿到一个单链表对象
        myLinkedList.addLast(10);
        myLinkedList.addLast(16);
        myLinkedList.addLast(23);
        myLinkedList.addLast(46);
        myLinkedList.addLast(37);
        myLinkedList.addLast(12);
        myLinkedList.addLast(19);
        myLinkedList.display();

        MyLinkedList myLinkedList1 = new MyLinkedList();//先拿到一个单链表对象
        myLinkedList1.addLast(1);
        myLinkedList1.addLast(3);
        myLinkedList1.addLast(5);
        myLinkedList1.addLast(7);
        myLinkedList1.addLast(9);
        myLinkedList1.addLast(13);
        myLinkedList1.display();

        createCut(myLinkedList.head,myLinkedList1.head);//调用
        ListNode   ret=getIntersectionNode(myLinkedList.head,myLinkedList1.head);
        System.out.println(ret.data);

Leetcode代码写法如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //1.求长度，走差值步
        int lenA=0;
        int lenB=0;
        ListNode pl=headA;
        ListNode ps=headB;
        //求长度
        while(pl!=null){
            lenA++;
            pl=pl.next;
        }
        while (ps!=null){
            lenB++;
            ps=ps.next;
        }
         pl=headA;
         ps=headB;
        int len=lenA-lenB;
        if(len<0){
            pl=headB;
            ps=headA;
            len=lenB-lenA;
        }
        //一定是pl指向的是最长的单链表
        for(int i=0;i<len;i++){//走差值步
            pl=pl.next;
        }
        //2、ps和pl一定是在同一个起跑线上
        while(ps!=pl ){//    && pl!=null && ps!=null
            ps=ps.next;
            pl=pl.next;
        }
        if(pl!=null){//代码走到这里表示pl和ps相遇了      pl==ps && 
            return pl;
        }
        return null;    
    }
}