【力扣刷题】回文链表、环形链表、合并两个有序链表

在这里插入图片描述

🐌个人主页： 🐌 叶落闲庭
💨我的专栏：💨
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和fast，fast指针比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;                        //返回合并后的链表的头节点，即哨兵位的下一个节点}