当前位置： 首页 > article >正文

【Java-数据结构】Java 链表面试题下 “最后一公里”：解决复杂链表问题的致胜法宝

article 2025/1/30 19:36:23

在这里插入图片描述

我的个人主页
我的专栏：Java-数据结构，希望能帮助到大家！！！点赞❤ 收藏❤
在这里插入图片描述
在这里插入图片描述

引言：
Java链表，看似简单的链式结构，却蕴含着诸多有趣的特性与奥秘，等待我们去挖掘。它就像一个神秘的宝藏迷宫，每一个特性都是隐藏在迷宫深处的珍贵宝藏。链表的环，如同迷宫中的循环通道，一旦进入，便可能陷入无尽的循环；链表节点的唯一性与重复性，仿佛迷宫中的岔路，有的道路独一无二，有的却似曾相识；而链表的长度变化，又如同迷宫的动态扩展与收缩。在接下来的题目中，你将化身为勇敢的探险家，深入链表特性的迷宫，运用你的编程智慧，解开一个个谜题。通过检测链表的环、分析节点的重复性以及精准计算链表长度，你将逐渐揭开链表神秘的面纱，领略数据结构背后的奇妙逻辑。

6.编写代码，以给定值x为基准将链表分割成两部分，所有⼩于x的结点排在⼤于或等于x的结点之前—链表分割

题目视图：
在这里插入图片描述

题目详解代码：

// 定义链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class PartitionList {
    public ListNode partition(ListNode pHead, int x) {
        // 创建两个虚拟头节点，分别用于存储小于 x 和大于等于 x 的节点
        ListNode smallDummy = new ListNode(0);
        ListNode largeDummy = new ListNode(0);
        // 分别指向两个新链表的当前节点
        ListNode smallTail = smallDummy;
        ListNode largeTail = largeDummy;

        // 遍历原链表
        ListNode current = pHead;
        while (current != null) {
            if (current.val < x) {
                // 如果当前节点的值小于 x，将其连接到 small 链表的尾部
                smallTail.next = current;
                smallTail = smallTail.next;
            } else {
                // 如果当前节点的值大于等于 x，将其连接到 large 链表的尾部
                largeTail.next = current;
                largeTail = largeTail.next;
            }
            // 移动到下一个节点
            current = current.next;
        }

        // 断开 large 链表的尾部，防止出现循环
        largeTail.next = null;
        // 将 small 链表和 large 链表连接起来
        smallTail.next = largeDummy.next;

        // 返回重新排列后的链表的头节点
        return smallDummy.next;
    }

    public static void main(String[] args) {
        // 创建测试链表 1 -> 4 -> 3 -> 2 -> 5 -> 2
        ListNode head = new ListNode(1);
        head.next = new ListNode(4);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(2);

        PartitionList solution = new PartitionList();
        int x = 3;
        // 调用 partition 方法进行重新排列
        ListNode newHead = solution.partition(head, x);

        // 打印重新排列后的链表
        ListNode current = newHead;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
    }
}

在这里插入图片描述

7.链表的回⽂结构。题目链接

题目视图：在这里插入图片描述

题目详解代码：

package Demo1_28;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-01-28
 * Time:20:04
 */
// 定义链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class PalindromeLinkedList {
    public boolean isPalindrome(ListNode A) {
        if (A == null || A.next == null) {
            return true;
        }
        // 步骤 1：找到链表的中间节点
        ListNode slow = A;
        ListNode fast = A;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 步骤 2：反转链表的后半部分
        ListNode secondHalf = reverseList(slow.next);
        // 步骤 3：比较链表的前半部分和反转后的后半部分
        ListNode p1 = A;
        ListNode p2 = secondHalf;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        // 步骤 4：恢复链表的原始结构
        slow.next = reverseList(secondHalf);
        return result;
    }

    // 反转链表的方法
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    public static void main(String[] args) {
        // 创建测试链表 1 -> 2 -> 2 -> 1
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(1);

        PalindromeLinkedList solution = new PalindromeLinkedList();
        // 调用 isPalindrome 方法判断链表是否为回文结构
        boolean isPalindrome = solution.isPalindrome(head);
        System.out.println(isPalindrome);
    }
}

在这里插入图片描述

8.输⼊两个链表，找出它们的第⼀个公共结点。—题目链接

题目视图：
在这里插入图片描述

题目详解代码：

package Demo1_28;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-01-28
 * Time:20:08
 */
// 定义链表节点类
class ListNode {
    int val;
    ListNode next;

    // 构造函数，用于初始化节点的值
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class IntersectionOfTwoLinkedLists {
    // 查找两个链表相交的起始节点的方法
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 如果其中一个链表为空，直接返回 null
        if (headA == null || headB == null) {
            return null;
        }
        // 初始化两个指针分别指向两个链表的头节点
        ListNode pA = headA;
        ListNode pB = headB;
        // 当两个指针不相等时，继续循环
        while (pA != pB) {
            // 如果 pA 到达链表 A 的末尾，将其指向链表 B 的头节点
            pA = pA == null ? headB : pA.next;
            // 如果 pB 到达链表 B 的末尾，将其指向链表 A 的头节点
            pB = pB == null ? headA : pB.next;
        }
        // 返回相交节点，如果不相交则返回 null
        return pA;
    }

    public static void main(String[] args) {
        // 创建示例链表
        // 链表 A: 1 -> 2 -> 3 -> 6 -> 7
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(2);
        headA.next.next = new ListNode(3);

        // 链表 B: 4 -> 5 -> 6 -> 7
        ListNode headB = new ListNode(4);
        headB.next = new ListNode(5);

        // 创建相交部分
        ListNode intersection = new ListNode(6);
        intersection.next = new ListNode(7);

        // 连接链表 A 和相交部分
        headA.next.next.next = intersection;
        // 连接链表 B 和相交部分
        headB.next.next = intersection;

        // 创建 IntersectionOfTwoLinkedLists 类的实例
        IntersectionOfTwoLinkedLists solution = new IntersectionOfTwoLinkedLists();
        // 调用 getIntersectionNode 方法查找相交节点
        ListNode result = solution.getIntersectionNode(headA, headB);
        if (result != null) {
            System.out.println("相交节点的值为: " + result.val);
        } else {
            System.out.println("两个链表不相交");
        }
    }
}

在这里插入图片描述

9.给你一个链表的头节点 head ，判断链表中是否有环。—题目链接

题目视图：在这里插入图片描述

题目详解代码：

// 定义链表节点类
class ListNode {
    int val;
    ListNode next;

    // 构造函数，用于初始化节点的值
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class LinkedListCycle {
    // 判断链表是否有环的方法
    public boolean hasCycle(ListNode head) {
        // 如果链表为空或者只有一个节点，肯定没有环
        if (head == null || head.next == null) {
            return false;
        }
        // 慢指针，初始指向头节点，每次移动一步
        ListNode slow = head;
        // 快指针，初始指向头节点的下一个节点，每次移动两步
        ListNode fast = head.next;
        // 当慢指针和快指针不相等时，继续循环
        while (slow != fast) {
            // 如果快指针到达链表末尾或者快指针的下一个节点是末尾，说明没有环
            if (fast == null || fast.next == null) {
                return false;
            }
            // 慢指针移动一步
            slow = slow.next;
            // 快指针移动两步
            fast = fast.next.next;
        }
        // 如果跳出循环，说明慢指针和快指针相遇了，链表有环
        return true;
    }

    public static void main(String[] args) {
        // 创建有环链表 1 -> 2 -> 3 -> 4 -> 2（环从节点 2 开始）
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);

        // 构建链表连接关系
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        // 形成环
        node4.next = node2;

        // 创建 LinkedListCycle 类的实例
        LinkedListCycle solution = new LinkedListCycle();
        // 调用 hasCycle 方法判断链表是否有环
        boolean result = solution.hasCycle(node1);
        System.out.println("链表是否有环: " + result);

        // 创建无环链表 1 -> 2 -> 3 -> 4
        ListNode nodeA = new ListNode(1);
        ListNode nodeB = new ListNode(2);
        ListNode nodeC = new ListNode(3);
        ListNode nodeD = new ListNode(4);

        // 构建无环链表连接关系
        nodeA.next = nodeB;
        nodeB.next = nodeC;
        nodeC.next = nodeD;

        // 再次调用 hasCycle 方法判断无环链表是否有环
        result = solution.hasCycle(nodeA);
        System.out.println("链表是否有环: " + result);
    }
}

在这里插入图片描述

10.给定⼀个链表，返回链表开始⼊环的第⼀个节点。 如果链表⽆环，则返回 NULL

—题目链接

题目视图：在这里插入图片描述

题目详解代码：

package Demo1_28;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-01-28
 * Time:20:15
 */
// 定义链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class LinkedListCycleII {
    public ListNode detectCycle(ListNode head) {
        // 如果链表为空或只有一个节点，肯定没有环
        if (head == null || head.next == null) {
            return null;
        }
        // 慢指针，初始指向头节点，每次移动一步
        ListNode slow = head;
        // 快指针，初始指向头节点，每次移动两步
        ListNode fast = head;
        boolean hasCycle = false;

        // 寻找是否有环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // 快慢指针相遇，说明有环
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }

        // 如果没有环，返回 null
        if (!hasCycle) {
            return null;
        }

        // 慢指针重新指向头节点
        slow = head;
        // 快慢指针都以每次一步的速度移动，再次相遇的节点就是环的入口节点
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        // 创建有环链表 1 -> 2 -> 3 -> 4 -> 2（环从节点 2 开始）
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);

        // 构建链表连接关系
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        // 形成环
        node4.next = node2;

        // 创建 LinkedListCycleII 类的实例
        LinkedListCycleII solution = new LinkedListCycleII();
        // 调用 detectCycle 方法找到环的入口节点
        ListNode result = solution.detectCycle(node1);
        if (result != null) {
            System.out.println("环的入口节点的值为: " + result.val);
        } else {
            System.out.println("链表中没有环");
        }

        // 创建无环链表 1 -> 2 -> 3 -> 4
        ListNode nodeA = new ListNode(1);
        ListNode nodeB = new ListNode(2);
        ListNode nodeC = new ListNode(3);
        ListNode nodeD = new ListNode(4);

        // 构建无环链表连接关系
        nodeA.next = nodeB;
        nodeB.next = nodeC;
        nodeC.next = nodeD;

        // 再次调用 detectCycle 方法判断无环链表是否有环
        result = solution.detectCycle(nodeA);
        if (result != null) {
            System.out.println("环的入口节点的值为: " + result.val);
        } else {
            System.out.println("链表中没有环");
        }
    }
}

在这里插入图片描述
所有的链表题目就分享到着了继续加油❤👍！！！


http://www.kler.cn/a/523200.html

相关文章：

  • HTML 标题
  • C++ ——— 仿函数
  • Nginx前端后端共用一个域名如何配置
  • Oracle Primavera P6 最新版 v24.12 更新 1/2
  • Spring事务和事务传播机制
  • GPU上没程序在跑但是显存被占用
  • 快速分析LabVIEW主要特征进行判断
  • Java面试题2025-并发编程基础（多线程、锁、阻塞队列）
  • Java基于SSM框架的互助学习平台小程序【附源码、文档】
  • GPS信号捕获【时间-频率空间搜索方法】
  • 指定dpkg安装deb包时的安装路径
  • SpringBoot 使用海康 SDK 和 flv.js 显示监控画面
  • objection的简单使用
  • 一图展示汽车和航空电子领域的安全和互操作性解决方案的概览
  • https数字签名手动验签
  • PythonFlask框架
  • Effective Objective-C 2.0 读书笔记—— objc_msgSend
  • 跨平台物联网漏洞挖掘算法评估框架设计与实现文献综述：物联网设备漏洞挖掘的挑战和机遇
  • iPhone SE（第三代） 设备详情图
  • 约瑟夫问题（信息学奥赛一本通-2037）
  • 具身智能体俯视全局的导航策略！TopV-Nav: 解锁多模态语言模型在零样本目标导航中的顶视空间推理潜力
  • 从源码深入理解One-API框架：适配器模式实现LLM接口对接
  • python Flask-Redis 连接远程redis
  • GWO优化决策树分类预测matlab
  • 硬脂酸单甘油酯（GMS）行业分析
  • LeetCode：509.斐波那契数