800字以上网站设计方案,网上销售型的企业网站,网站推广软件免费下载安装,论坛网站开发的目的和意义#x1f40c;个人主页#xff1a; #x1f40c; 叶落闲庭 #x1f4a8;我的专栏#xff1a;#x1f4a8; c语言 数据结构 javaEE 操作系统 Redis 石可破也#xff0c;而不可夺坚#xff1b;丹可磨也#xff0c;而不可夺赤。 刷题篇 一、回文链表1.1 题目描述1.2 思路分… 个人主页 叶落闲庭 我的专栏 c语言 数据结构 javaEE 操作系统 Redis 石可破也而不可夺坚丹可磨也而不可夺赤。 刷题篇 一、回文链表1.1 题目描述1.2 思路分析1.3 代码演示 二、环形链表2.1 题目描述2.2 思路分析2.3 代码演示 三、合并两个有序链表3.1 题目描述3.2 思路分析3.3 代码演示 一、回文链表
1.1 题目描述 给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。 1.2 思路分析 首先是要对该链表进行非空校验若是空链表直接返回fasle否则执行其它逻辑按照回文链表的规律可以有这样一个思路若它是回文链表可先找到他的前半个回文链表的最后一个节点通过这个节点就能找到开始回文的下半个链表的最后一个节点从该节点处将后半个回文链表进行整体反转然后再定义指针进行遍历从前半个回文链表的头开始作为p1指针后半个回文链表的头作为p2指针遍历整个回文链表判断它们的值是否相同若不相同则不是回文链表否则就是回文链表。 1.3 代码演示
public boolean isPalindrome(ListNode head) {//非空判断if (head null) {return false;}//找到回文链表前一段的最后一个节点ListNode firstHalfEnd endOfFirstList(head);//找到回文链表反转后的第一个节点ListNode firstHaftStart reverse(firstHalfEnd.next);//设置标记boolean result true;//设置遍历指针ListNode p1 head;ListNode p2 firstHalfStart;while(result p2 ! null) {if(p1.val ! p2.val) {result false;}p1 p1.next;p2 p2.next;}//恢复链表firstHaftEnd.next reverse(firstHalfEnd.next);return result;}public static ListNode reverse(ListNode head) {ListNode prev null;ListNode curr head;while (curr ! null) {ListNode temp curr.next;curr.next prev;prev curr;curr temp;}return prev;}public static ListNode endOfFirstList(ListNode head) {//设置快慢指针进行查找ListNode fast head;ListNode slow head;while (fast.next ! null fast.next.next ! null) {slow slow.next;fast fast.next.next;}return slow;}二、环形链表
2.1 题目描述 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。 2.2 思路分析 先进行非空校验若head为null字直接返回false,否则进行其它代码定义快慢指针slow和fastfast指针比slow指针快走两步while循环进行遍历条件是slow不等于fast遍历整个链表循环内是快慢指针的执行当链表存在环时fast指针总会多转几圈从而追上慢指针slow此时两个指针均指向同一个节点表示该链表存在环跳出循环返回true,若是在循环中fast指向了空或者fast.next指向了空表示该链表是正常的单向链表直接返回false即可。 2.3 代码演示
public boolean hasCycle(ListNode head) {if (head null) {return false;}ListNode fast head.next;ListNode slow head;while (slow ! fast) {if (fast null || fast.next null) {return false;}//fast指针每次比slow指针快走两步//若该链表存在环则这两个指针会进入环中//fast总有机会比slow多转n圈从而追上slow//此时跳出循环表示该链表是环形来链表fast fast.next.next;slow slow.next;}return true;}三、合并两个有序链表
3.1 题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 3.2 思路分析 按照题目要求可以先对空值进行校验若两个链表均为空则直接返回空若只有一个链表为空则直接返回另一个链表否则进行其它代码定义一个哨兵节点并定义一个指向它的的指针当两个链表均不为空时以此为条件开始遍历在循环中判断两个链表当前的节点值的大小情况若链表1的值小则将哨兵位的下一个节点指向链表1否则则将哨兵位的下一个节点指向链表2然后prev指向prev.next继续遍历链表循环结束时若链表长度不等则较长的链表直接将剩余的节点加到prev的next下返回合并后的链表的头节点即哨兵位的下一个节点。 3.3 代码演示
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1 null list2 null) {return null;}if(list1 null list2 ! null) {return list2;}if(list1 ! null list2 null) {return list1;}//定义一个哨兵位节点ListNode preHead new ListNode(-1);//定义一个指针指向哨兵位作为遍历指针ListNode prev preHead;//当链表都不为空时开始遍历while(list1 ! null list2 ! null) {if(list1.val list2.val) { //遍历链表比较链表当前节点的值的大小prev.next list1; //若链表1的值小则将哨兵位的下一个节点指向链表1list1 list1.next; //链表1继续遍历} else {prev.next list2; //若链表2的值小则将哨兵位的下一个节点指向链表2list2 list2.next; //链表2继续遍历}prev prev.next; //prev继续遍历链表}prev.next list1 null ? list2 : list1; //若链表长度不等则较长的链表直接将剩余的节点加到prev的next下即可return preHead.next; //返回合并后的链表的头节点即哨兵位的下一个节点}
