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

力扣-Hot100-链表其一【算法学习day.34】

news 2025/7/1 15:13:40

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.相交链表

题目链接:160. 相交链表 - 力扣（LeetCode）

题面:

基本分析:我们假设公共链表长度为c，A链表前面长度为a，B链表前面长度为b，我们假设指针p1指向headA，指针p2指向headB，那么p1到达如上图的相交节点c1，需要走的步数为a+b+c,p2同理，所以我们可以先让p1走到尽头，然后让p1指向headB继续走，p2同理，如果两指针相遇，相遇点就是相交节点

代码:

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode n1 = new ListNode();ListNode n2 = new ListNode();n1 = headA;n2 = headB;int flag = 0;while(n1!=n2){n1 = n1.next;n2 = n2.next;if(n1==null&&flag<3){n1 = headB;flag++;}if(n2==null&&flag<3){n2 = headA;flag++;}if(flag==3)break;}if(flag==3)return null;return n1;}
}

2.回文链表

题目链接:234. 回文链表 - 力扣（LeetCode）

题面:

基本分析:我是通过先遍历一遍把值存起来然后判断的暴力做法，不符合题目要求，可以看看力扣的大佬题解

代码:

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {int[] arr = new int[100005];int count = 0;for(ListNode i = head;i!=null;i=i.next){arr[count++] = i.val;}int l =0;int r = count-1;while(l<=r){if(arr[l]!=arr[r])return false;l++;r--;}return true;}
}

3.环形链表

题目链接:141. 环形链表 - 力扣（LeetCode）

题面:

基本分析:因为题目限制链表长度最大为10000，所以可以一直遍历来暴力判断

代码:

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if(head==null)return false;int count = 0;ListNode node = new ListNode();node = head;while(true){node = node.next;if(node==null)return false;count++;if(count==10005)break;}return true;}
}