力扣-数据结构-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);
    }
}

后言

上面是数据结构相关的习题，下一篇文章会将其他相关的习题。