力扣-数据结构-4【算法学习day.75】

前言

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

习题

1.链表最大孪生和

题目链接:2130. 链表最大孪生和 - 力扣（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 int pairSum(ListNode head) {int[] arr= new int[100005];int count = 0;for(ListNode i = head;i!=null;i=i.next){arr[count++] = i.val;}int ans = -1;for(int i = 0;i<=(count/2)-1;i++){ans = Math.max(ans,(arr[i]+arr[count-1-i]));}return ans;}
}

2.重排链表

题目链接:143. 重排链表 - 力扣（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 void reorderList(ListNode head) {if(head!=null&&head.next!=null){ListNode slow = head;ListNode fast = head;ListNode fpre = head;while(fast!=null&&fast.next!=null){fast = fast.next.next;fpre = slow;slow = slow.next;}fpre.next = null;ListNode rtall = null;ListNode rhead = null;ListNode pre = rtall;while(slow!=null){ListNode node = slow.next;slow.next = pre;pre = slow;if(node==null){rhead = slow;}slow = node;}int count = 1;ListNode fhead = new ListNode();ListNode apre = fhead;// for(ListNode i = head;i!=null;i=i.next){//     System.out.println(i.val);// }//     System.out.println("___________________________");// for(ListNode i = rhead;i!=null;i=i.next){//      System.out.println(i.val);// }for(ListNode i = head,j = rhead;i!=null||j!=null;){if(count%2==1&&i!=null){apre.next = i;apre = i;i=i.next;}else if(count%2==0&&j!=null){apre.next = j;apre = j;j = j.next;}count++;}}}
}

3.环形数组是否存在循环

题目链接:457. 环形数组是否存在循环 - 力扣（LeetCode）

分析:可以使用并查集也可以使用快慢双指针

代码:

class Solution {int[] p;public boolean circularArrayLoop(int[] nums) {int n = nums.length;p = new int[n];for(int i = 0;i<n;i++){p[i] = i;}for(int i = 0;i<n;i++){int flag = nums[i]+i;if(flag>=n)flag%=n;if(flag<0){while(flag<0){flag+=n;}}if(i==flag)continue;if(nums[i]*nums[flag]>0){if(connected(i,flag)){return true;}union(i,flag);}}// for(int i = 0;i<n;i++){//     System.out.println(p[i]);// }return false;}public int find2(int x){if(x!=p[x]){p[x] = find2(p[x]);}return p[x];}public void union(int x,int y){int px = find2(x);int py = find2(y);if(px!=py){p[px] = py;}}public boolean connected(int x,int y){return find2(x)==find2(y);}
}