[Java数据结构与算法]经典链表面试题详解

木井巳

发布于 2025-12-16 09:33:13

1290

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

思路：

需要用到两个引用(初始的时候指向链表的第二个节点)，一个引用用于检查节点是否是要被删除的节点，一个用于改变链表的指向
需要注意检查链表的第一个节点是否为要被删除的节点，建议把该操作放到其余节点删除操作的后面

具体如下：

public class RemoveAllVal {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;

    void removeAllVal(int val) {
        if (head == null) return;

        ListNode cur = head.next;
        ListNode prev = head;

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

二、反转一个单链表

思路：

先将链表的第一个节点的next置空；再遍历整个链表，将每个节点进行头插操作
注意不要忘了记录下一个节点的地址

具体如下：

public class Reverse {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;

    void reverse() {
        if (head == null) return;

        ListNode cur = head.next;
        head.next = null;

        while (cur != null) {
            ListNode latter = cur.next;
            cur.next = head;
            head = cur;
            cur = latter;
        }
    }
}

三、返回链表的中间节点

思路：

使用两个引用，初始时都指向第一个节点
一个每次走两步，另一个每次走一步
等快的引用为空时或者快引用的所指节点的下一个节点为空时（节点个数分别考虑奇数个和偶数个），慢的引用所指位置即为中间节点

具体如下：

public class MiddleNode {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;

    ListNode middleNode() {
        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;
    }
}

四、链表的回文结构

思路：

先找到链表的中间节点（双引用）
再反转后半部分
然后用两个引用分别从前后开始往中间走同时判断每个节点的值是否相等，当两引用相遇时，即表示是回文结构；
注意不可以使用走得较快的指针（找中间节点时用的指针）
节点个数为偶数个时怎么办？判断前一个引用的 next 是否等于后一个引用，若是，则表示是回文结构

public class ChkPalindrome {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;

    public boolean chkPalindrome() {
        if (head == null) return true;
        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 next = cur.next;
            cur.next = slow;
            slow = cur;
            cur = next;
        }

        while (head != slow) {  //判断回文
            if (head.val != slow.val) return false;
            if (head.next == slow) return true;    //节点个数为偶数个时的处理
            head = head.next;
            slow = slow.next;
        }

        return true;
    }
}

五、返回链表倒数第 k 个节点的值

思路：

使用双引用，先让快的走 k-1 步，再让其跟慢的一起走，每次走一步
当快引用的next为空时，慢引用所指位置即为所求
注意 k的取值范围(0,list.size()]，为防止空指针异常，可以边走边判断是否为空

具体如下：

public class TheKthLastNodeVal {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;

    int TheKthLastNodeVal(int k) {
        if (head == null) return -1;
        if (k <= 0) return -1;
        ListNode fast = head;
        ListNode slow = head;
        int count = 0;
        while (k-1 != count) {
            fast = fast.next;
            if (fast == null) {
                return -1;
            }
            count++;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
}

六、分割链表

思路：

将原链表分割成两个子链表（former和latter），前者放小于x的节点，后者放大于x的节点；
利用四个引用（former/front/latter/last）：ff、fl、lf、ll 进行排列操作
遍历原链表，将每个节点的值与x进行比较，如果小于x则放入former，否则放入latter；
最后将 fl 和 lf 进行链接，再返回 ff 即可
注意两个子链表第一次放入节点如何操作？把两个引用均指向新放入的节点
如果链表的数据都比x小/大呢？即former或latter可能为空：前一个子链表为空时，需要手动返回后面子链表的第一个节点，即 ll；当后面的子链表为空时，无需手动返回
不要忘了把最后一个节点的 next 置空

具体如下：

public class Partition {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;

    public ListNode partition (int x) {
        ListNode cur = head;

        ListNode ff = null;
        ListNode fl = null;
        ListNode lf = null;
        ListNode ll = null;

        while (cur != null) {
            if (cur.val < x) {
                if (ff == null) {
                    ff = fl = cur;
                } else {
                    fl.next = cur;
                    fl = fl.next;
                }
            } else {
                if (lf == null) {
                    lf = ll = cur;
                } else {
                    ll.next = cur;
                    ll = ll.next;
                }
            }
            cur = cur.next;
        }
        if (ff == null) {       //第一个子链表为空
            return lf;
        }
//        if (lf == null) {     //第二个子链表为空，没必要写
//            return ff;
//        }
        fl.next = lf;           //把两个子链表拼接起来

        if (lf != null) {       //强制把尾节点的next置空
            ll.next = null;
        }

        return ff;
    }
}

七、合并两个有序链表

思路：

定义一个新引用 newHead 作为合并后链表第一个节点的前一个节点(为了能够找到拼接后的链表)，我们暂且称之为指引节点
再定义一个新引用 temp 指向该指引节点（确保拼接时 newHead 始终指向指引节点）
使用两个链表的 head 遍历链表并比较值的大小，让 temp 指向更小的那个节点并确保 temp 始终指向当前值最小的节点
当循环结束，判断哪个链表不为空(用 head 判断)，拼接尾部
注意循环需要保证两个链表的 head 均不为空
最后返回 newHead 的 next 即可

具体如下：

public class MergeTwoList {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
}

public class Test {
    MergeTwoList.ListNode mergeTwoList(MergeTwoList.ListNode headA,
                                       MergeTwoList.ListNode headB) {
        MergeTwoList.ListNode newHead = new MergeTwoList.ListNode(-1);
        MergeTwoList.ListNode temp = newHead;

        while (headA!=null && headB!=null) {
            if (headA.val < headB.val) {
                temp.next = headA;
                temp = headA;
                headA = headA.next;
            } else {
                temp.next = headB;
                temp = headB;
                headB = headB.next;
            }
        }

        if (headA != null) {
            temp.next = headA;
        }
        if (headB != null) {
            temp.next = headB;
        }

        return newHead.next;
    }
}

八、返回两个链表的第一个交点

思路：

用两个指针分别遍历两个链表，每次走一步，当两指针相遇时即为交点；
当两个链表长度不同时，先求两个链表的长度，求出差值，再让指向长链表的指针先走差值步，然后两指针一起走
注意若指向长链表的指针为空，说明两个链表没有相交(此时指向短链表的应已经为空)，则返回null

具体如下：

public class GetIntersectionNode {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
}

public class Test {
    public GetIntersectionNode.ListNode getIntersectionNode(GetIntersectionNode.ListNode headA,
                                                            GetIntersectionNode.ListNode headB) {
        GetIntersectionNode.ListNode pl = headA;    //指向长链表的指针
        GetIntersectionNode.ListNode ps = headB;    //指向短链表的指针

        int lenA = 0;   //长链表的长度
        int lenB = 0;   //短链表的长度

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

        while (len != 0) {  //指向长链表的指针先走len步
            pl = pl.next;
            len--;
        }

        while (pl != ps) {  //两指针一起走
            pl = pl.next;
            ps = ps.next;
        }

        if (pl == null) return null;  //当长指针为空时，短指针逻辑上来说应比长指针走得快，此时已经为空，说明两链表没有交点

        return pl;
    }
}

九、判断链表中是否有环

思路：

使用两个初始位置在 head 的引用，第一个一次走两步，第二个一次走一步
当两个引用相遇时，则代表链表里有环
注意当第一个引用和其 next 所指的节点为空时，就不要再进入循环了

具体实现如下：

public class HasCycle {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;

    public boolean hasCycle() {
        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;
    }
}

十、返回链表中环的入口点

思路：

第一步：先判断链表是否有环
第二步：让 slow 从起点开始走（即head位置处），让 fast 从相遇点开始走
两者以相同的速度每次走一步，等到再次相遇时，所处位置即为入环点

原理：

设链表的第一个节点（称为起点）到环的入口点的距离是 X ，链表环的长度是 C ，两个引用相遇点到环的入口点的距离是 Y
第一个（fast）引用相遇时所走的距离：X + C + C - Y
第二个（slow）引用相遇时所走的距离：X + C - Y
由两者的速度具有两倍的关系，在时间相等的情况下，可以得到两者所走的距离也是具有两倍关系的，即：X + 2C - Y = 2 ( X + C - Y )。解这个方程可以得到 X = Y。
通过上述的计算，我们得到了一个结论：链表起点到环入口点的距离 X 和两引用相遇点到环入口点的距离 Y 是相等的，那我们就可以将引用 slow 放到链表起点，此时 fast 还在相遇点，我们让两个引用分别在两个点以相同的速度（一次走一步）同时走，程序运行的时间是一样的，等两个引用最终相遇时，他们所走的距离一定是一样的，此时他们所处的位置就是环的入口

具体实现如下：

public class DetectCycle {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;

    public ListNode detectCycle() {
        // 判断是否有环
        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) return null;    // 该链表没有环

        // 寻找入环点
        slow = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }
}

通过以上几道经典的链表面试题，相信读者对链表的原理结构已经十分了解了～

完

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-10-19，如有侵权请联系 cloudcommunity@tencent.com 删除

java