网站建设淘宝类目,适合做网站的图片,微信抽奖小程序,网站开发的研究方法我的个人主页 我的专栏#xff1a;Java-数据结构#xff0c;希望能帮助到大家#xff01;#xff01;#xff01;点赞❤ 收藏❤ 引言#xff1a; Java链表#xff0c;看似简单的链式结构#xff0c;却蕴含着诸多有趣的特性与奥秘#xff0c;等待我们去挖掘。它就像一…
我的个人主页 我的专栏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 - 2ListNode 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:* UserLenovo* 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 - 1ListNode 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:* UserLenovo* 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) {// 如果其中一个链表为空直接返回 nullif (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;}// 返回相交节点如果不相交则返回 nullreturn pA;}public static void main(String[] args) {// 创建示例链表// 链表 A: 1 - 2 - 3 - 6 - 7ListNode headA new ListNode(1);headA.next new ListNode(2);headA.next.next new ListNode(3);// 链表 B: 4 - 5 - 6 - 7ListNode 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 - 4ListNode 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:* UserLenovo* 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;}}// 如果没有环返回 nullif (!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 - 4ListNode 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(链表中没有环);}}
} 所有的链表题目就分享到着了继续加油❤
