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

Ne0inhk

— 9 min read
【Java-数据结构】Java 链表面试题下 “最后一公里”：解决复杂链表问题的致胜法宝
在这里插入图片描述

我的个人主页
我的专栏：Java-数据结构，希望能帮助到大家！！！点赞❤ 收藏❤

在这里插入图片描述


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

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

题目视图：

题目详解代码：

// 定义链表节点类classListNode{int val;ListNode next;ListNode(int x){ val = x; next =null;}}publicclassPartitionList{publicListNodepartition(ListNode pHead,int x){// 创建两个虚拟头节点，分别用于存储小于 x 和大于等于 x 的节点ListNode smallDummy =newListNode(0);ListNode largeDummy =newListNode(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;}publicstaticvoidmain(String[] args){// 创建测试链表 1 -> 4 -> 3 -> 2 -> 5 -> 2ListNode head =newListNode(1); head.next =newListNode(4); head.next.next =newListNode(3); head.next.next.next =newListNode(2); head.next.next.next.next =newListNode(5); head.next.next.next.next.next =newListNode(2);PartitionList solution =newPartitionList();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.链表的回⽂结构。题目链接

题目视图：

题目详解代码：

packageDemo1_28;/** * Created with IntelliJ IDEA. * Description: * User：Lenovo * Date:2025-01-28 * Time:20:04 */// 定义链表节点类classListNode{int val;ListNode next;ListNode(int x){ val = x; next =null;}}publicclassPalindromeLinkedList{publicbooleanisPalindrome(ListNodeA){if(A==null||A.next ==null){returntrue;}// 步骤 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;}// 反转链表的方法privateListNodereverseList(ListNode head){ListNode prev =null;ListNode curr = head;while(curr !=null){ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp;}return prev;}publicstaticvoidmain(String[] args){// 创建测试链表 1 -> 2 -> 2 -> 1ListNode head =newListNode(1); head.next =newListNode(2); head.next.next =newListNode(2); head.next.next.next =newListNode(1);PalindromeLinkedList solution =newPalindromeLinkedList();// 调用 isPalindrome 方法判断链表是否为回文结构boolean isPalindrome = solution.isPalindrome(head);System.out.println(isPalindrome);}}
在这里插入图片描述

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

题目视图：

题目详解代码：

packageDemo1_28;/** * Created with IntelliJ IDEA. * Description: * User：Lenovo * Date:2025-01-28 * Time:20:08 */// 定义链表节点类classListNode{int val;ListNode next;// 构造函数，用于初始化节点的值ListNode(int x){ val = x; next =null;}}publicclassIntersectionOfTwoLinkedLists{// 查找两个链表相交的起始节点的方法publicListNodegetIntersectionNode(ListNode headA,ListNode headB){// 如果其中一个链表为空，直接返回 nullif(headA ==null|| headB ==null){returnnull;}// 初始化两个指针分别指向两个链表的头节点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;}// 返回相交节点，如果不相交则返回 nullreturn pA;}publicstaticvoidmain(String[] args){// 创建示例链表// 链表 A: 1 -> 2 -> 3 -> 6 -> 7ListNode headA =newListNode(1); headA.next =newListNode(2); headA.next.next =newListNode(3);// 链表 B: 4 -> 5 -> 6 -> 7ListNode headB =newListNode(4); headB.next =newListNode(5);// 创建相交部分ListNode intersection =newListNode(6); intersection.next =newListNode(7);// 连接链表 A 和相交部分 headA.next.next.next = intersection;// 连接链表 B 和相交部分 headB.next.next = intersection;// 创建 IntersectionOfTwoLinkedLists 类的实例IntersectionOfTwoLinkedLists solution =newIntersectionOfTwoLinkedLists();// 调用 getIntersectionNode 方法查找相交节点ListNode result = solution.getIntersectionNode(headA, headB);if(result !=null){System.out.println("相交节点的值为: "+ result.val);}else{System.out.println("两个链表不相交");}}}
在这里插入图片描述

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

题目视图：

题目详解代码：

// 定义链表节点类classListNode{int val;ListNode next;// 构造函数，用于初始化节点的值ListNode(int x){ val = x; next =null;}}publicclassLinkedListCycle{// 判断链表是否有环的方法publicbooleanhasCycle(ListNode head){// 如果链表为空或者只有一个节点，肯定没有环if(head ==null|| head.next ==null){returnfalse;}// 慢指针，初始指向头节点，每次移动一步ListNode slow = head;// 快指针，初始指向头节点的下一个节点，每次移动两步ListNode fast = head.next;// 当慢指针和快指针不相等时，继续循环while(slow != fast){// 如果快指针到达链表末尾或者快指针的下一个节点是末尾，说明没有环if(fast ==null|| fast.next ==null){returnfalse;}// 慢指针移动一步 slow = slow.next;// 快指针移动两步 fast = fast.next.next;}// 如果跳出循环，说明慢指针和快指针相遇了，链表有环returntrue;}publicstaticvoidmain(String[] args){// 创建有环链表 1 -> 2 -> 3 -> 4 -> 2（环从节点 2 开始）ListNode node1 =newListNode(1);ListNode node2 =newListNode(2);ListNode node3 =newListNode(3);ListNode node4 =newListNode(4);// 构建链表连接关系 node1.next = node2; node2.next = node3; node3.next = node4;// 形成环 node4.next = node2;// 创建 LinkedListCycle 类的实例LinkedListCycle solution =newLinkedListCycle();// 调用 hasCycle 方法判断链表是否有环boolean result = solution.hasCycle(node1);System.out.println("链表是否有环: "+ result);// 创建无环链表 1 -> 2 -> 3 -> 4ListNode nodeA =newListNode(1);ListNode nodeB =newListNode(2);ListNode nodeC =newListNode(3);ListNode nodeD =newListNode(4);// 构建无环链表连接关系 nodeA.next = nodeB; nodeB.next = nodeC; nodeC.next = nodeD;// 再次调用 hasCycle 方法判断无环链表是否有环 result = solution.hasCycle(nodeA);System.out.println("链表是否有环: "+ result);}}
在这里插入图片描述

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

—题目链接

题目视图：

题目详解代码：

packageDemo1_28;/** * Created with IntelliJ IDEA. * Description: * User：Lenovo * Date:2025-01-28 * Time:20:15 */// 定义链表节点类classListNode{int val;ListNode next;ListNode(int x){ val = x; next =null;}}publicclassLinkedListCycleII{publicListNodedetectCycle(ListNode head){// 如果链表为空或只有一个节点，肯定没有环if(head ==null|| head.next ==null){returnnull;}// 慢指针，初始指向头节点，每次移动一步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;}}// 如果没有环，返回 nullif(!hasCycle){returnnull;}// 慢指针重新指向头节点 slow = head;// 快慢指针都以每次一步的速度移动，再次相遇的节点就是环的入口节点while(slow != fast){ slow = slow.next; fast = fast.next;}return slow;}publicstaticvoidmain(String[] args){// 创建有环链表 1 -> 2 -> 3 -> 4 -> 2（环从节点 2 开始）ListNode node1 =newListNode(1);ListNode node2 =newListNode(2);ListNode node3 =newListNode(3);ListNode node4 =newListNode(4);// 构建链表连接关系 node1.next = node2; node2.next = node3; node3.next = node4;// 形成环 node4.next = node2;// 创建 LinkedListCycleII 类的实例LinkedListCycleII solution =newLinkedListCycleII();// 调用 detectCycle 方法找到环的入口节点ListNode result = solution.detectCycle(node1);if(result !=null){System.out.println("环的入口节点的值为: "+ result.val);}else{System.out.println("链表中没有环");}// 创建无环链表 1 -> 2 -> 3 -> 4ListNode nodeA =newListNode(1);ListNode nodeB =newListNode(2);ListNode nodeC =newListNode(3);ListNode nodeD =newListNode(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("链表中没有环");}}}
在这里插入图片描述


所有的链表题目就分享到着了继续加油❤👍！！！

Read more

【C++初阶】：C++类和对象（上）:类的定义 & 类的实例化 & this指针

【C++初阶】：C++类和对象（上）:类的定义 & 类的实例化 & this指针

🎈主页传送门:良木生香 🔥个人专栏:《C语言》 《数据结构-初阶》 《程序设计》《鼠鼠的C++学习之路》 🌟人为善,福随未至,祸已远行;人为恶,祸虽未至,福已远离 前言：我们为了更加高效的入门C++，特意花费了三篇文章的篇幅讲解C语言和C++的不同之处，以及C++针对C语言的不足做出了哪些改变，有命名空间、输入输出、缺省参数等等方面的内容，具体的文章链接我会放在本篇文章的最后，大家可以继续参考。有了前三这篇文章的铺垫，我们就可以正式入门C++了！那么我们就从最基础的“类和对象”开始学习。在“类和对象这一板块中，我将花费大约三篇文章的篇幅进行讲解，话不多说，直接进入今天的主题吧：类和对象（上）。 目录 一、类的定义 1.1、类定义格式 1.2、访问限定符 1.3、成员命名
【2024 Year-End Summary】C++自学分享

【2024 Year-End Summary】C++自学分享

目录 [ C 语言 ] [ 数据结构 ] [ 算法 ] [ C++ ] [Linux] [Mysql] [Redis 文档学习] [Docker 云原生] [Git] [Qt] 转眼大学就过了一年半，希望自己可以保持学习₍₍Ϡ(੭•̀ω•́)੭✧⃛ 在刚上大一的时候用的是纸质笔记本，后来东西越学越多，就开始使用语雀文档，文章也有部分同步到 ZEEKLOG 上了，很高兴能够对大家有所帮助~ 博客之星的文章一直不知道写些什么，想着对专栏做一个整理叭 下面的标题/网课名 就是 学习链接的传送门，自学的资料也都是免费的，开头就不多说了，学就好啦 [ C 语言 ] hh 这是多少小伙伴梦开始的地方 网课： * 【浙江大学】C语言入门与进阶 翁恺（全129讲）_哔哩哔哩_bilibili 书籍： * C Primer Plus * C
【Linux系统】C/C++的调试器gdb/cgdb，从入门到精通

【Linux系统】C/C++的调试器gdb/cgdb，从入门到精通

各位读者大佬好，我是落羽！一个坚持不断学习进步的学生。 如果您觉得我的文章还不错，欢迎多多互三分享交流，一起学习进步！ 也欢迎关注我的blog主页:落羽的落羽 文章目录 * 一、调试前的预备知识 * 二、gdb/cgdb的使用 * 1. 启动，查看代码 * 2. 基础调试命令 * 3. 监视变量相关命令 * 4. 设置条件断点 一、调试前的预备知识 程序发布的方式有两种，debug模式和release模式。 * debug模式：生成的可执行程序中会包含程序的调试信息，便于程序员进行调试代码。 * release模式：会剥离或不生成这些调试信息。这使得文件更小，但也意味着调试器几乎无法工作，release版本程序无法进行调试。 Linux的gcc/g++，按照我们之前的写法gcc -o $@ $^，默认生成的是release版本的程序，是无法进行调试的。要在命令后加-g选项，指定以debug方式发布，debug模式下的程序我们才能进行调试。 gcc -o $@ $^ -g 二、gdb/cgdb的使用
C++ 拷贝构造函数与赋值运算符：深拷贝与浅拷贝的核心辨析

C++ 拷贝构造函数与赋值运算符：深拷贝与浅拷贝的核心辨析

C++ 拷贝构造函数与赋值运算符：深拷贝与浅拷贝的核心辨析 💡 学习目标：掌握拷贝构造函数与赋值运算符的定义及调用场景，理解深拷贝与浅拷贝的本质区别，能够在实际开发中避免内存泄漏与野指针问题。 💡 学习重点：拷贝构造函数的触发条件、浅拷贝的缺陷、深拷贝的实现方法、赋值运算符的重载原则。 一、拷贝构造函数的概念与触发场景 ✅ 结论：拷贝构造函数是一种特殊的构造函数，用于通过一个已存在的对象创建一个新对象，其参数必须是本类对象的常量引用（const 类名&）。 1.1 拷贝构造函数的语法格式 class 类名 {public:// 普通构造函数 类名(参数列表);// 拷贝构造函数 类名(const 类名& other);}; ⚠️ 注意事项： 1. 拷贝构造函数的参数必须是常量引用，使用 const 防止实参被修改，使用引用避免无限递归调用拷贝构造函数。 2. 如果没有手动定义拷贝构造函数，编译器会自动生成一个默认拷贝构造函数，实现简单的成员变量值拷贝。 1.2 拷贝构造函数的触发条件